/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
2 人の人がおり，0 と 1 の番号がついています． また，0 で初期化された変数 x があります． これから 2 人はゲームを行います． ゲームは N ラウンドからなり，i 回目 (1 \leq i \leq N) のラウンドでは，次の操作が行われます．
- 人 S_i が以下のいずれかの操作をする．
- x を x \oplus A_i で置き換える．ただしここで \oplus はbitごとの排他的論理和を表す．
- 何もしない．
人 0 の目標は，最終的に x=0 にすることで，逆に人 1 の目標は，最終的に x \neq 0 にすることです．
2 人が最適に行動する時，最終的に x が 0 になるかどうかを判定してください．
1 つの入力につき，T 個のテストケースに答えてください．
制約
- 1 \leq T \leq 100
- 1 \leq N \leq 200
- 1 \leq A_i \leq 10^{18}
- S は
0と1のみからなる長さ N の文字列 - 入力される数は全て整数である．
入力
入力は以下の形式で標準入力から与えられる． 入力の 1 行目は以下のとおりである．
T
そして，T 個のテストケースが続く． これらはそれぞれ以下の形式で与えられる．
N A_1 A_2 \cdots A_N S
出力
各テストケースについて，最終的に x=0 となる場合は 0，そうでない場合は 1 と出力せよ．
各テストケースごとに改行せよ．
入力例 1
3 2 1 2 10 2 1 1 10 6 2 3 4 5 6 7 111000
出力例 1
1 0 0
1 つ目のテストケースでは，人 1 が x を 0 \oplus 1=1 で置き換えると，人 0 の操作に依らず，最終的に x \neq 0 になります．
2 つ目のテストケースでは，人 1 がどちらの操作を行っても，人 0 が適切な操作をすれば x=0 にできます．
Score : 400 points
Problem Statement
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):
- Person S_i does one of the following:
- Replace x with x \oplus A_i, where \oplus represents bitwise XOR.
- Do nothing.
Person 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.
Determine whether x becomes 0 at the end of the game when the two persons play optimally.
Solve T test cases for each input file.
Constraints
- 1 \leq T \leq 100
- 1 \leq N \leq 200
- 1 \leq A_i \leq 10^{18}
- S is a string of length N consisting of
0and1. - All numbers in input are integers.
Input
Input is given from Standard Input in the following format. The first line is as follows:
T
Then, T test cases follow. Each test case is given in the following format:
N A_1 A_2 \cdots A_N S
Output
For each test case, print a line containing 0 if x becomes 0 at the end of the game, and 1 otherwise.
Sample Input 1
3 2 1 2 10 2 1 1 10 6 2 3 4 5 6 7 111000
Sample Output 1
1 0 0
In 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.
In the second test case, regardless of the choice of Person 1, Person 0 can make x=0 with a suitable choice.