{"problem":{"name":"Strange Nim","description":{"content":"Takahashi and Aoki are playing a stone-taking game. Initially, there are $N$ piles of stones, and the $i$\\-th pile contains $A_i$ stones and has an associated integer $K_i$. Starting from Takahashi, T","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc091_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi and Aoki are playing a stone-taking game. Initially, there are $N$ piles of stones, and the $i$\\-th pile contains $A_i$ stones and has an associated integer $K_i$.\nStarting from Takahashi, Takahashi and Aoki take alternate turns to perform the following operation:\n\n*   Choose a pile. If the $i$\\-th pile is selected and there are $X$ stones left in the pile, remove some number of stones between $1$ and $floor(X/K_i)$ (inclusive) from the pile.\n\nThe player who first becomes unable to perform the operation loses the game. Assuming that both players play optimally, determine the winner of the game. Here, $floor(x)$ represents the largest integer not greater than $x$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 200$\n*   $1 \\leq A_i,K_i \\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $K_1$\n$:$\n$A_N$ $K_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc091_d","tags":[],"sample_group":[["2\n5 2\n3 3","Aoki\n\nInitially, from the first pile at most $floor(5/2)=2$ stones can be removed at a time, and from the second pile at most $floor(3/3)=1$ stone can be removed at a time.\n\n*   If Takahashi first takes two stones from the first pile, from the first pile at most $floor(3/2)=1$ stone can now be removed at a time, and from the second pile at most $floor(3/3)=1$ stone can be removed at a time.\n*   Then, if Aoki takes one stone from the second pile, from the first pile at most $floor(3/2)=1$ stone can be removed at a time, and from the second pile no more stones can be removed (since $floor(2/3)=0$).\n*   Then, if Takahashi takes one stone from the first pile, from the first pile at most $floor(2/2)=1$ stone can now be removed at a time, and from the second pile no more stones can be removed.\n*   Then, if Aoki takes one stone from the first pile, from the first pile at most $floor(1/2)=0$ stones can now be removed at a time, and from the second pile no more stones can be removed.\n\nNo more operation can be performed, thus Aoki wins. If Takahashi plays differently, Aoki can also win by play accordingly."],["3\n3 2\n4 3\n5 1","Takahashi"],["3\n28 3\n16 4\n19 2","Aoki"],["4\n3141 59\n26535 897\n93 23\n8462 64","Takahashi"]],"created_at":"2026-03-03 11:01:14"}}