A - Xor Battle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

2 人の人がおり,01 の番号がついています. また,0 で初期化された変数 x があります. これから 2 人はゲームを行います. ゲームは N ラウンドからなり,i 回目 (1 \leq i \leq N) のラウンドでは,次の操作が行われます.

  • S_i が以下のいずれかの操作をする.
    • xx \oplus A_i で置き換える.ただしここで \oplus はbitごとの排他的論理和を表す.
    • 何もしない.

0 の目標は,最終的に x=0 にすることで,逆に人 1 の目標は,最終的に x \neq 0 にすることです.

2 人が最適に行動する時,最終的に x0 になるかどうかを判定してください.

1 つの入力につき,T 個のテストケースに答えてください.

制約

  • 1 \leq T \leq 100
  • 1 \leq N \leq 200
  • 1 \leq A_i \leq 10^{18}
  • S01 のみからなる長さ 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 つ目のテストケースでは,人 1x0 \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 0 and 1.
  • 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.