AT_abc417_g [ABC417G] Binary Cat

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} $ .

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 $ Q $ lines. The $ i $ -th line $ (1\leq i\leq Q) $ should contain the answer to the $ i $ -th query.

### Sample Explanation 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. ### 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.