AT_arc213_b [ARC213B] Hamming Distance is not 1

非負整数 $ q,L,R\;(q \in \{ 0,1\}, \; L \leq R) $ が与えられます。 以下のすべての条件を満たす集合 $ S $ について考えます。 - $ S $ は $ L $ 以上 $ R $ 以下の互いに相異なる整数からなる。 - $ a \in S, \; b \in S, \; a \neq b $ のとき、 $ a $ と $ b $ は $ 2 $ 進表記で $ 2 $ 桁以上異なる。 より厳密には、 $ \left\lfloor\frac{a}{2^i}\right\rfloor $ と $ \left\lfloor\frac{b}{2^i}\right\rfloor $ の偶奇が異なるような非負整数 $ i $ が $ 2 $ 個以上存在する。 - 上の $ 2 $ 条件を満たすもののうち、要素数が最大となる。 $ q=0 $ のとき、このような集合 $ S $ の要素数を求めてください。 $ q=1 $ のとき、このような集合 $ S $ を一つ構築してください。 $ 1 $ つの入力ファイルにつき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式で与えられる。 > $ q $ $ L $ $ R $

答えを合計 $ T $ 行で出力せよ。 $ t $ 個目のテストケースの答えを $ t $ 行目に出力せよ。 各テストケースでは、 $ q=0 $ ならば条件を満たす集合 $ S $ の要素数を出力せよ。 $ q=1 $ ならば条件を満たすような集合 $ S $ に対して $ B_i=\begin{cases} 1 \; (S \text{ に } i \text{ が含まれる }) \\ 0 \; (S \text{ に } i \text{ が含まれない }) \end{cases} $ として、以下の形式で出力せよ。 > $ B_L $ $ B_{L+1} $ $ \dots $ $ B_R $ 条件を満たす $ S $ が複数存在する場合はどれを出力してもよい。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、 $ S=\{0,3\} $ は条件を満たします。 $ S=\{1,2\} $ も条件を満たすため正解となります。 $ 2 $ つ目のテストケースでは、条件を満たす $ S $ は $ \{1,2\} $ のみで、その要素数は $ 2 $ です。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 0 \leq q \leq 1 $ - $ 0 \leq L \leq R \leq 10^{18} $ - 全てのテストケースにおける $ q(R-L) $ の総和は $ 5\times 10^6 $ 以下 - 入力される値は全て整数