410468: GYM104023 M String Master

Rousong the Fox is a string master who can handle a wide variety of strings with ease. For example, he can braid noodles with his tongue. Likewise, he is good with string data types in computer programming.

One night, Rousong has a dream, in which he picks an infinitely long string out of the bowl when eating noodles. On closer inspection, it is a binary string containing only zeros and ones, concatenated by $$$0,1,10,11,\dots$$$. Formally, let's define string $$$s^0=0$$$, and $$$s^i=s^{i-1}+(i)_2$$$ for each integer $$$i>0$$$, where $$$a+b$$$ denotes the concatenation of string $$$a$$$ and $$$b$$$, and $$$(i)_2$$$ denotes the binary form of integer $$$i$$$ without leading zeros. Consequently, the infinitely long string Rousong dreamed of is $$$s^\infty=011011100101\dots$$$.

Since the length of $$$s^\infty$$$ is too large, Rousong only wants to focus on the substring from the $$$l$$$-th character to the $$$r$$$-th character, denoted as $$$s^\infty_{l,r}$$$. He wants to find the substring of length $$$n$$$ within the string $$$s^\infty_{l,r}$$$ with the largest lexicographical order. Formally, please find the index $$$i$$$ within $$$l \le i \le r-n+1$$$ that maximizes the lexicographical order of $$$s^\infty_{i,i+n-1}$$$. Can you help Rousong solve this problem before he wakes up?

For two binary strings of the same length $$$a$$$ and $$$b$$$, we say that string $$$a$$$ is lexicographically greater than string $$$b$$$ if for the first index $$$i$$$ where $$$a$$$ and $$$b$$$ differ, the $$$i$$$-th character of $$$a$$$ is $$$1$$$ and of $$$b$$$ is $$$0$$$.

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$), indicating the number of test cases.

Each test case contains three integers $$$l,r,n$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$1 \le n \le \min(r-l+1,10^6)$$$) in a single line, indicating the range to be focused on and the length of the substring.

It is guaranteed that $$$\sum n \le 10^6$$$ over all test cases.

For each test case, output the substring with the largest lexicographical order in a single line.

6
6 13 3
1 9 9
1 1451419198 10
987 6543 21
1123 581321 34
1000010 1000030 18

110
011011100
1111111111
111111111100000000010
1111111111111111000000000000000100
000111110011010000

For the first test case of the sample, $$$s^\infty=01101\underline{11001011}10111\dots$$$, so $$$s^\infty_{6,13}=11001011$$$. The substrings of length $$$3$$$ are $$$110,100,001,010,101,011$$$. The one with the largest lexicographical order is $$$110$$$.