408450: GYM103119 G Game on Sequence

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Game on Sequencetime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Grammy is playing a game with her roommate Alice on a sequence $$$A$$$ with $$$n$$$ non-negative integers $$$A_1,A_2,\dots,A_n$$$. The rules of the game are described as follows.

  1. They play the game by moving the single token on the sequence, initially the token is at position $$$k$$$.
  2. Grammy takes the first move, and they take moves alternatively.
  3. In any move with the token at position $$$i$$$, the current player must move the token to the next position $$$j$$$ such that $$$j>i$$$ and $$$A_j$$$ differs from $$$A_i$$$ on at most one bit in binary representation.
  4. The player who can't make any legal move loses the game.

They play this game many times and the sequence can be modified many times. Grammy wants to ask you for some initial states who will win the game if both play optimally.

Input

The first line of input contains 2 integers $$$n$$$ and $$$m$$$ ($$$1\leq n,m\leq 200\,000$$$), denoting the length of the sequence and the number of operations.

The second line contains $$$n$$$ integers $$$A_1,A_2,\dots,A_n$$$ ($$$0\leq A_i\leq 255$$$), denoting the sequence $$$A$$$.

The next $$$m$$$ lines each contains 2 integers $$$op$$$ ($$$1\leq op\leq 2$$$) and $$$k$$$, denoting each operation:

  • $$$op=1$$$ means a modification on the sequence. Grammy will append an integer $$$k$$$ ($$$0\leq k\leq 255$$$) at the end of the sequence so the sequence becomes $$$A_1, A_2, \dots, A_{N+1}$$$ where $$$N$$$ is the current length of the sequence before modification.
  • $$$op=2$$$ means a new game starts with the token at position $$$k$$$ ($$$1\leq k\leq N$$$), where $$$N$$$ is the current length of the sequence. You need to predict the winner of this game.
Output

For each operation with $$$op=2$$$, output one line containing "Grammy" if Grammy will win, or "Alice" if Alice will win when they play optimally.

ExampleInput
5 5
1 2 3 4 5
1 6
2 5
1 7
2 5
2 1
Output
Alice
Grammy
Alice

加入题单

上一题 下一题 算法标签: