G - Binary Cat Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 625 点

問題文

文字列 S_0,S_1 を S_0= 0, S_1= 1 と定義します。

クエリが Q 個与えられるので、順に処理してください。
i 番目 (1\leq i\leq Q) のクエリでは、3 つの整数の組 (L_i,R_i,X_i) が与えられます。

S_{L_i} と S_{R_i} をこの順に連結した文字列を S_{i+1} とする。 その後、S_{i+1} の X_i 文字目を求める。

なお、X_i が S_{i+1} の長さ以下であることは保証される。

制約

  • 1\leq Q\leq 5\times 10^5
  • 0\leq L_i,R_i\leq i
  • 1\leq X_i\leq 10^{18}
  • X_i は S_{i+1} の長さ以下である。
  • 入力はすべて整数

入力

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

Q
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q

出力

Q 行出力せよ。 i 行目 (1\leq i\leq Q) には、i 番目のクエリに対する答えを出力せよ。

入力例 1

7
0 1 1
0 0 2
1 1 1
2 3 2
2 4 3
5 4 2
6 7 6

出力例 1

0
0
1
1
1
1
1

各クエリは次のように処理されます。

  • 1 番目のクエリでは S_0=0 と S_1=1 を連結し、S_2=01 となります。S_2 の 1 文字目は 0 であるため、1 行目には 0 を出力します。
  • 2 番目のクエリでは S_0=0 と S_0=0 を連結し、S_3=00 となります。S_3 の 2 文字目は 0 であるため、2 行目には 0 を出力します。
  • 3 番目のクエリでは S_1=1 と S_1=1 を連結し、S_4=11 となります。S_4 の 1 文字目は 1 であるため、3 行目には 1 を出力します。
  • 4 番目のクエリでは S_2=01 と S_3=00 を連結し、S_5=0100 となります。S_5 の 2 文字目は 1 であるため、4 行目には 1 を出力します。
  • 5 番目のクエリでは S_2=01 と S_4=11 を連結し、S_6=0111 となります。S_6 の 3 文字目は 1 であるため、5 行目には 1 を出力します。
  • 6 番目のクエリでは S_5=0100 と S_4=11 を連結し、S_7=010011 となります。S_7 の 2 文字目は 1 であるため、6 行目には 1 を出力します。
  • 7 番目のクエリでは S_6=0111 と S_7=010011 を連結し、S_8=0111010011 となります。S_8 の 6 文字目は 1 であるため、7 行目には 1 を出力します。

Score : 625 points

Problem Statement

Define strings S_0 and S_1 as S_0= 0 and S_1= 1.

You are given Q queries, so process them in order.
In the i-th query (1\leq i\leq Q), you are given a triple of integers (L_i,R_i,X_i).

Let S_{i+1} be the string obtained by concatenating S_{L_i} and S_{R_i} in this order. Then, find the X_i-th character of S_{i+1}.

It is guaranteed that X_i is at most the length of S_{i+1}.

Constraints

  • 1\leq Q\leq 5\times 10^5
  • 0\leq L_i,R_i\leq i
  • 1\leq X_i\leq 10^{18}
  • X_i is at most the length of S_{i+1}.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q

Output

Output Q lines. The i-th line (1\leq i\leq Q) should contain the answer to the i-th query.

Sample Input 1

7
0 1 1
0 0 2
1 1 1
2 3 2
2 4 3
5 4 2
6 7 6

Sample Output 1

0
0
1
1
1
1
1

Each query is processed as follows:

  • In the first query, concatenate S_0=0 and S_1=1 to get S_2=01. The first character of S_2 is 0, so output 0 on the first line.
  • In the second query, concatenate S_0=0 and S_0=0 to get S_3=00. The second character of S_3 is 0, so output 0 on the second line.
  • In the third query, concatenate S_1=1 and S_1=1 to get S_4=11. The first character of S_4 is 1, so output 1 on the third line.
  • In the fourth query, concatenate S_2=01 and S_3=00 to get S_5=0100. The second character of S_5 is 1, so output 1 on the fourth line.
  • In the fifth query, concatenate S_2=01 and S_4=11 to get S_6=0111. The third character of S_6 is 1, so output 1 on the fifth line.
  • In the sixth query, concatenate S_5=0100 and S_4=11 to get S_7=010011. The second character of S_7 is 1, so output 1 on the sixth line.
  • In the seventh query, concatenate S_6=0111 and S_7=010011 to get S_8=0111010011. The sixth character of S_8 is 1, so output 1 on the seventh line.