Aurora tocmai a ajuns învăţătoare la şcoala din cartier. În prima zi de şcoală ea a aşezat toţi cei N copii din şcoală într-un singur rând, apoi a numerotat copiii de la 1 la N, de la stânga la dreapta. Acum Aurora pune M întrebări de tipul: ″există doi copii x şi y (x≤y) astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi în şir între copilul x şi copilul y (inclusiv x şi y) să fie exact K; dacă da, daţi un exemplu!″?
Cerinţă
Scrieţi un program care să răspundă la întrebările Aurorei.
Date de intrare
Pe prima linie a fişierului de intrare diff.in se vor afla numerele naturale N şi M, separate printr-un spaţiu, reprezentând numărul de copii şi respectiv numărul de întrebări ale Aurorei. Următoarea linie va conţine N numere 0 sau 1 separate prin câte un spaţiu; al i-lea număr de pe linie va fi 0 în cazul în care copilul i este fată, respectiv 1, în cazul în care copilul i este băiat. Următoarele M linii vor conţine cele M întrebări, câte o întrebare pe o linie. Pe cea de a i-a linie dintre cele M se află numărul natural Ki, specificat în cea de a i-a întrebare a Aurorei.
Date de ieşire
În fişierul de ieşire diff.out veţi scrie M linii. Pe cea de a i-a linie (1≤i≤M) se vor scrie două numere naturale x şi y (1≤x≤y≤N), cu semnificaţia că diferenţa dintre numărul de băieţi şi numărul de fete situaţi în şir între copilul x şi copilul y (inclusiv x şi y) este exact Ki sau -1 în cazul în care nu există soluţie.
Restricţii
• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 200 000
• -1 000.000.000 ≤ Ki ≤ 1 000 000 000, pentru 1≤i≤M
• Pot exista mai multe răspunsuri corecte la o întrebare; afişaţi oricare dintre acestea.
• În răspunsul la o întrebare x poate fi egal cu y, caz în care este vorba de un singur copil.
• Pentru 20% din teste N ≤ 300 şi M ≤ 300
• Pentru 40% din teste N ≤ 100 000 şi M ≤ 500
• Pentru 40% din teste N ≤ 3 000 şi M ≤ 200 000
Exemple
diff.in
diff.out
Explicaţii
10 4
0 0 1 0 0 1 1 0 1 1
3
-3
10
0
6 10
1 5
-1
2 3
Există 10 copii. Aurora formulează 4 întrebări.
La prima întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 3. O soluţie posibilă este x=6 şi y=10 (între 6 şi 10 există 4 băieţi şi o fată).
La a doua întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie -3. O soluţie posibilă este x=1 şi y=5 (între 1 şi 5 există 4 fete şi un băiat).
La a treia întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 10. Nu există soluţie în acest caz.
La a patra întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 0. O soluţie posibilă este x=2 şi y=3 (între 2 şi 3 există o fată şi un băiat).