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.

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$

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

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

4777