Binary Fibonacci String (BFS)#2527
We are familiar with the Fibonacci sequence (, , , , , , ). What if we define a similar sequence for strings?
We define the following sequence:
\mathrm{BFS}(0) = \text{"0"} and \mathrm{BFS}(1) = \text{"1"} (here, and are strings, not the numbers or ).
For all n > 1, \mathrm{BFS}(n) = \mathrm{BFS}(n - 2) + \mathrm{BFS}(n - 1) (here, denotes string concatenation; that is, the -th string is the concatenation of the previous two strings).
The first few strings in this sequence are: , , , , , and so on.
Your task is to find the -th string of the sequence and print all of its characters from position to position , inclusive. All indices are -based.
The first line of the input contains an integer (T \leq 100) denoting the number of test cases.
Each test case is described as follows:
Three integers , , with 0 \leq N, i, j \leq 2^{31} - 1, i \leq j, and j - i \leq 10000. You may assume that and are valid positions (i.e., 0 \leq i, j < \textit{length} of ).
For each test case, print the substring of from the -th to the -th position, inclusive, on a single line.
Example 1