Given the current word, it is easy to reconstruct what that word looked like before one blink. Let's call it a reverse blink. We can find the initial word by repeating the reverse blink ~X~ times. This solution is of the complexity ~\mathcal O(NX)~, which is good enough to gain ~50\%~ of points.

After a bit of scribbling on paper, it is easily noticed that the reverse blinking is periodical, meaning that after ~P~ reverse blinks, the word will transform into the initial form. Hence, if we repeat the reverse blink ~k \times P + l~ times, it is the same as we repeated it just ~l~ times.

The solution requires only finding the number ~P~ (which can be done by simply repeating the reverse blink until the word is transformed into the initial form) and then repeat the reverse blink ~X \bmod P~ times.

It is shown that ~P~ is always less than ~N~, meaning the total complexity of this algorithm is at most ~\mathcal O(N^2)~, which is fast enough for ~100\%~ of points.