== include(page="template/taskheader" task_id="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!"?

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!"?

h2. Cerinţă

h2. Cerinta

Scrieţi un program care să răspundă la întrebările Aurorei.
h2. 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.

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.

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

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

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$
* $-1 000.000.000 ≤ $K{~i~}$ ≤ 1 000 000 000, pentru 1 ≤ i ≤ M$

* $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$

* 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$

h2. Exemplu

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).
== include(page="template/taskfooter" task_id="diff") ==

4777