레이팅 미적용Jakov and Toni, the two best players in the world, will face each other in the finals
of the world championship in krastoboj.
Krastoboj is a game played by two players on a sequence of positive integers. The
players take turns making moves, and the player who cannot make a move loses
the game. At the very beginning, there is only one sequence of positive integers
on the board - the initial sequence.
In one move, a player chooses one of the existing sequences and one number \(x\)
that appears in that sequence. Then they delete all occurrences of \(x\) in the chosen
sequence, thereby splitting the sequence into several new sequences separated at
the positions where \(x\) appeared.
A sequence of numbers - the template for the final match - has been found. It is known that the initial
sequence in the final will be some contiguous subsequence of this template sequence. You are given \(q\)
scenarios. For each scenario, can you determine who the winner will be, assuming that both Toni and
Jakov play optimally and that Toni makes the first move?
The first line contains two positive integers \(n\) and \(q\) (\(1 \le n\), \(q \le 10^{5}\)).
The second line contains a sequence of positive integers \(a_{1}\), \(a_{2}\), . . . , \(a_{n}\) (\(1 \le a_{i} \le 32\) for each \(i = 1\), 2, . . . , n).
The following \(q\) lines each contain two integers \(l_{i}\) and \(r_{i}\) (\(1 \le l_{i} \le r_{i} \le n\)), the boundaries of the contiguous
subsequence considered in the \(i\)-th scenario.
For each query, print on a separate line either Toni or Jakov, the name of the winner in the \(i\)-th scenario.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | n, \(q \le 10\) |
2 | 11점 | n, \(q \le 1000\), \(a_{i} \le 2\) |
3 | 18점 | n, \(q \le 1000\) |
4 | 14점 | \(a_{i} \le 2\) |
5 | 23점 | \(a_{li} = a_{ri}\) for every \(i = 1\), . . . , q |
6 | 29점 | No additional constraints. |
6 4
1 3 2 3 1 2
1 1
2 3
2 4
1 3Toni
Jakov
Toni
Toni10 5
3 3 3 1 2 2 1 2 2 1
2 3
9 10
5 6
5 8
3 7Toni
Jakov
Toni
Toni
ToniClarification of the first example: In the third scenario, Toni chooses x = 2, which splits the sequence
into two sequences of length 1. Whichever sequence Jakov chooses next, Toni will choose the remaining
one, after which Jakov will have no possible moves left.