AT_abc417_g [ABC417G] Binary Cat

文字列 $ 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} $ の長さ以下であることは保証される。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 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 $ を出力します。 ### 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 $ は $ S_{i+1} $ の長さ以下である。 - 入力はすべて整数