BFS (Binary Fibonacci String)
Ми знайомі з послідовністю Фібоначчі (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-й символ у окремому рядку.