{"problem":{"name":"Xor Battle","description":{"content":"There are two persons, numbered $0$ and $1$, and a variable $x$ whose initial value is $0$. The two persons now play a game. The game is played in $N$ rounds. The following should be done in the $i$\\-","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc045_a"},"statements":[{"statement_type":"Markdown","content":"There are two persons, numbered $0$ and $1$, and a variable $x$ whose initial value is $0$. The two persons now play a game. The game is played in $N$ rounds. The following should be done in the $i$\\-th round ($1 \\leq i \\leq N$):\n\n*   Person $S_i$ does one of the following:\n    *   Replace $x$ with $x \\oplus A_i$, where $\\oplus$ represents bitwise XOR.\n    *   Do nothing.\n\nPerson $0$ aims to have $x=0$ at the end of the game, while Person $1$ aims to have $x \\neq 0$ at the end of the game.\nDetermine whether $x$ becomes $0$ at the end of the game when the two persons play optimally.\nSolve $T$ test cases for each input file.\n\n## Constraints\n\n*   $1 \\leq T \\leq 100$\n*   $1 \\leq N \\leq 200$\n*   $1 \\leq A_i \\leq 10^{18}$\n*   $S$ is a string of length $N$ consisting of `0` and `1`.\n*   All numbers in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format. The first line is as follows:\n\n$T$\n\nThen, $T$ test cases follow. Each test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc045_a","tags":[],"sample_group":[["3\n2\n1 2\n10\n2\n1 1\n10\n6\n2 3 4 5 6 7\n111000","1\n0\n0\n\nIn the first test case, if Person $1$ replaces $x$ with $0 \\oplus 1=1$, we surely have $x \\neq 0$ at the end of the game, regardless of the choice of Person $0$.\nIn the second test case, regardless of the choice of Person $1$, Person $0$ can make $x=0$ with a suitable choice."]],"created_at":"2026-03-03 11:01:13"}}