Description

Problem B - BFS (Binary Fibonacci String)

We are familiar with the Fibonacci sequence (1, 1, 2, 3, 5, 8, ...). What if we define a similar sequence for strings? Sounds interesting? Let‘s see.

We define the follwing sequence:

BFS(0) = 0
BFS(1) = 1 (here "0" and "1" are strings, not simply the numerical digit, 0 or 1)

for all (n > 1)
BFS(n) = BFS(n - 2) + BFS(n - 1) (here, + denotes the string concatenation operation). (i.e. the n-th string in this sequence is a concatenation of a previous two strings).

So, the first few strings of this sequence are: 0, 1, 01, 101, 01101, and so on.

Your task is to find the N-th string of the sequence and print all of its characters from the i-th to j-th position, inclusive. (All of N, i, j are 0-based indices)

Input

The first line of the input file contains an integer T (T ≤ 100) which denotes the total number of test cases. The description of each test case is given below:

Three integers N, i, j (0 ≤ N, i, j ≤ 2³¹ - 1) and (i ≤ j and j - i ≤ 10000). You can assume that, both i and j will be valid indices (i.e.0 ≤ i, j < length of BFS(N)) .

Output

For each test case, print the substring from the i-th to the j-th position of BFS(N) in a single line.

Sample Input

3

3 1 2

1 0 0

9 5 12

Sample Output

01

1

10101101

题意：0，1， 01， 101， 01101.....每个串都是前两个串的连接，输出第n个串的第i到j位

思路：因为第n个串是第n-2个串+第n-1个串，所以我们所以我们像对树的搜索一样，递归下去

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 111;

ll f[maxn];
int n, x, y;

void init() {
	f[0] = f[1] = 1;
	for (int i = 2; i < maxn; i++)
		f[i] = f[i-1] + f[i-2];
}

void bfs(ll l, ll r, int cur, int sign) {
	if (y < l || x > r)
		return;
	if (l == r) {
		printf("%d", sign);
		return;
	}
	bfs(l, l+f[cur-2]-1, cur-2, sign);
	bfs(l+f[cur-2], r, cur-1, 1-sign);
}

int main() {
	init();
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &x, &y);	
		int cnt;
		for (int i = 0; i <= 50; i++)
			if ((i % 2 == n % 2) && f[i] > y) {
				cnt = i;
				break;
			}
		int sign = cnt % 2;
		bfs(0, f[cnt]-1, cnt, sign);
		printf("\n");
	}
	return 0;
}