БСФ (Бинарная Строка Фибоначчи)
Мы знакомы с последовательностью Фибоначчи (1, 1, 2, 3, 5, 8, ...). А что будет, если мы определим аналогичную последовательность для строк? Звучит интересно? Давайте посмотрим.
Мы определим эту последовательность так:
BFS(0) = 0
BFS(1) = 1 (здесь "0" и "1" являются строками, а не просто числами 0 или 1)
для всех (n > 1)
BFS(n) = BFS(n - 2) + BFS(n - 1) (здесь + обозначает операцию конкатенации). (то есть, n-ая строка в этой последовательности представляет собой объединение двух предыдущих строк).
Итак, первые несколько строк в этой последовательности такие: 0, 1, 01, 101, 01101 и так далее.
Ваша задача: для каждой заданной n-ой строки этой последовательности найти и вывести все её элементы с i-ой по j-ую позицию включительно (все числа n, i, j нумеруются начиная с 0).
Входные данные
Первая строка содержит количество тестов t (t ≤ 100). Описание каждого теста имеет вид:
Три целых числа n, i, j (0 ≤ n, i, j ≤ 2^31 - 1) и (i ≤ j и j - i ≤ 10000). Можно также предположить, что i и j будут индексами существующих элементов строки (т.е. 0 ≤ i, j < length_ of BFS(n)).
Выходные данные
Для каждого теста вывести искомую подстроку BFS(n) с i-го по j-ый символ в отдельной строке.