Tokitsukaze and Duel
Contest: Codeforces Round 573 (Div. 1)
Difficulty rating: 2300
Tags: brute force, games, greedy

"Duel!"

Betting on the lovely princess Claris, the duel between Tokitsukaze and Quailty has started.

There are $$$n$$$ cards in a row. Each card has two sides, one of which has color. At first, some of these cards are with color sides facing up and others are with color sides facing down. Then they take turns flipping cards, in which Tokitsukaze moves first. In each move, one should choose exactly $$$k$$$ consecutive cards and flip them to the same side, which means to make their color sides all face up or all face down. If all the color sides of these $$$n$$$ cards face the same direction after one's move, the one who takes this move will win.

Princess Claris wants to know who will win the game if Tokitsukaze and Quailty are so clever that they won't make mistakes.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

The second line contains a single string of length $$$n$$$ that only consists of $$$0$$$ and $$$1$$$, representing the situation of these $$$n$$$ cards, where the color side of the $$$i$$$-th card faces up if the $$$i$$$-th character is $$$1$$$, or otherwise, it faces down and the $$$i$$$-th character is $$$0$$$.

Output format:
Print "once again" (without quotes) if the total number of their moves can exceed $$$10^9$$$, which is considered a draw.

In other cases, print "tokitsukaze" (without quotes) if Tokitsukaze will win, or "quailty" (without quotes) if Quailty will win.

Note that the output characters are case-sensitive, and any wrong spelling would be rejected.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, no matter how Tokitsukaze moves, there would be three cards with color sides facing the same direction after her move, and Quailty can flip the last card to this direction and win.

In the second example, no matter how Tokitsukaze moves, Quailty can choose the same card and flip back to the initial situation, which can allow the game to end in a draw.

In the third example, Tokitsukaze can win by flipping the leftmost five cards up or flipping the rightmost five cards down.

The fourth example can be explained in the same way as the second example does.

Example input:
4 2
0101

Example output:
quailty

Example input:
6 1
010101

Example output:
once again

Editorial:
If a player can make a move from a situation to that situation again, this player will not lose. Except for some initial situations, one can move from almost every situation to itself. Based on these two conclusions, we can get a solution.
If Tokitsukaze cannot win after her first move, she cannot win in the future. In this case, we can quickly check if $$$k$$$ is so limited that she cannot win.
After her first move, it is possible that Quailty wins in the next move. If he cannot, in order to prevent failure, he can just leave the situation to his opponent by doing useless flipping and thus result in a draw.
Therefore, we can check if no matter how Tokitsukaze moves, Quailty has no chance to win after his first move. It can be easily checked linearly if we do some precalculation and enumerate Tokitsukaze's first move. Alternatively, we can find and check the pattern of initial situations in which Quailty can win.