F - Again ABC String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

長さ N の A,B,C からなる文字列 S のうち、以下の条件を満たすものの個数を 2 で割ったあまり を求めてください。

  • S の 1 文字目から i 文字目までからなる文字列を S_i とする。S_i に含まれる A,B,C の個数をそれぞれ A_i,B_i,C_i とする。このとき、1 \le i \le N を満たす任意の整数 i に対し、以下が成り立つ。
    • A_i-B_i \le X
    • B_i-C_i \le Y
    • C_i-A_i \le Z

この問題は、T ケース与えられます。

制約

  • 1 \le T \le 10
  • 1 \le N \le 10^9
  • 0 \le X,Y,Z \le 10^9
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N X Y Z

出力

各ケースについて、答えを出力せよ。

入力例 1

1
3 2 1 0

出力例 1

0

条件を満たす文字列は、AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC の 8 個があります。よって、解は 0 です。

入力例 2

10
1 22 9 92
14 7 74 39
23 50 8 6
93 40 9 60
68 8 47 64
11 68 18 24
3 26 54 8
46 17 90 86
86 76 45 55
80 68 79 62

出力例 2

1
0
0
0
1
1
1
0
1
0

Score : 1100 points

Problem Statement

Consider strings of length N consisting of A, B, and C. Among them, find the number of strings that satisfy the following condition, modulo 2:

  • Let S_i be the string formed by the first i characters of S. Also let A_i, B_i, and C_i be the numbers of A's, B's, and C's in S_i, respectively. For all i such that 1 \le i \le N, the following holds:
    • A_i-B_i \le X
    • B_i-C_i \le Y
    • C_i-A_i \le Z

You have T test cases to solve.

Constraints

  • 1 \le T \le 10
  • 1 \le N \le 10^9
  • 0 \le X,Y,Z \le 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each case is in the following format:

N X Y Z

Output

For each case, print the answer.

Sample Input 1

1
3 2 1 0

Sample Output 1

0

8 strings satisfy the condition: AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC. Therefore the answer is 0.

Sample Input 2

10
1 22 9 92
14 7 74 39
23 50 8 6
93 40 9 60
68 8 47 64
11 68 18 24
3 26 54 8
46 17 90 86
86 76 45 55
80 68 79 62

Sample Output 2

1
0
0
0
1
1
1
0
1
0