BFS (İkili Fibonacci Sırası)
Biz Fibonacci ardıcıllığını bilirik (1, 1, 2, 3, 5, 8, ...). Bəs əgər biz sətirlər üçün buna bənzər bir ardıcıllıq yaratsaq necə olar? Maraqlı səslənir? Gəlin baxaq.
Bu ardıcıllığı belə təyin edirik:
BFS(0) = 0
BFS(1) = 1 (burada "0" və "1" sadəcə ədədlər 0 və ya 1 deyil, sətirlərdir)
bütün (n > 1) üçün
BFS(n) = BFS(n - 2) + BFS(n - 1) (burada + birləşdirmə əməliyyatını göstərir). Yəni, bu ardıcıllıqda n-ci sətir əvvəlki iki sətirin birləşməsidir.
Beləliklə, bu ardıcıllığın ilk bir neçə sətiri belədir: 0, 1, 01, 101, 01101 və s.
Sizin vəzifəniz: verilmiş hər bir N-ci sətir üçün onun i-ci mövqeyindən j-ci mövqeyinə qədər (hər iki mövqe daxil olmaqla) bütün elementlərini tapmaq və çıxarmaqdır (bütün N, i, j ədədləri 0-dan başlayaraq nömrələnir).
Giriş verilənləri
Giriş faylının ilk sətiri ümumi testlərin sayını göstərən tam ədəd T (T ≤ 100) ehtiva edir. Hər bir testin təsviri aşağıda verilmişdir:
Üç tam ədəd N, i, j (0 ≤ N, i, j ≤ 2^31 - 1) və (i ≤ j və j-i ≤ 10000). Həmçinin, i və j sətirin mövcud elementlərinin indeksləri olacağını qəbul edə bilərsiniz (yəni 0 ≤ i, j < length of BFS(N)).
Çıxış verilənləri
Verilmiş hər bir test üçün BFS(N) sətirinin i-ci mövqeyindən j-ci mövqeyinə qədər olan alt sətiri ayrı-ayrı sətirdə çıxarın.