{"problem":{"name":"01 Game","description":{"content":"There are $N$ squares called square $1$, square $2$, $\\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \\ldots, N-1$. Initially, $M$ of the squares have $0$ or $1","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc151_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ squares called square $1$, square $2$, $\\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \\ldots, N-1$.\nInitially, $M$ of the squares have $0$ or $1$ written on them. Specifically, for each $i = 1, 2, \\ldots, M$, $Y_i$ is written on square $X_i$. The other $N-M$ squares have nothing written on them.\nTakahashi and Aoki will play a game against each other. The two will alternately act as follows, with Takahashi going first.\n\n*   Choose a square with nothing written yet, and write $0$ or $1$ on that square. Here, it is forbidden to make two adjacent squares have the same digit written on them.\n\nThe first player to be unable to act loses; the other player wins.\nDetermine the winner when both players adopt the optimal strategy for their own victory.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^{18}$\n*   $0 \\leq M \\leq \\min\\lbrace N, 2 \\times 10^5 \\rbrace$\n*   $1 \\leq X_1 \\lt X_2 \\lt \\cdots \\lt X_M \\leq N$\n*   $Y_i \\in \\lbrace 0, 1\\rbrace$\n*   $X_i + 1 = X_{i+1} \\implies Y_i \\neq Y_{i+1}$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc151_c","tags":[],"sample_group":[["7 2\n2 0\n4 1","Takahashi\n\nHere is one possible progression of the game.\n\n1.  Takahashi writes $0$ on square $6$.\n2.  Aoki writes $1$ on square $1$.\n3.  Takahashi writes $1$ on square $7$.\n\nThen, Aoki cannot write $0$ or $1$ on any square, so Takahashi wins."],["3 3\n1 1\n2 0\n3 1","Aoki\n\nSince every square already has $0$ or $1$ written at the beginning, Takahashi, who goes first, cannot act, so Aoki wins."],["1000000000000000000 0","Aoki"]],"created_at":"2026-03-03 11:01:14"}}