diff

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 $K_i$, 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 $K_i$ sau -1 în cazul în care nu există soluţie.

Restricţii şi precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 200 000
• $-1\ 000\ 000\ 000 \le K_i \le 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

Exemplu

diff.in

10 4
0 0 1 0 0 1 1 0 1 1
3
-3
10
0	

diff.out

6 10
1 5
-1
2 3

Explicaţie

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).