scaune

Se consideră $ns$ scaune numerotate de la $1$ la $ns$, aranjate în cerc.
De exemplu, pentru $ns=20$ aşezarea scaunelor este dată în figura de mai jos.

Pe fiecare din aceste scaune este aşezat un copil. Primul copil stă pe scaunul $1$, iar ultimul pe scaunul $ns$.

Pe lângă cele $ns$ scaune deja ocupate, alţi $nc$ copii ($1 \leq nc \leq ns$) aşteaptă să se elibereze un loc.

La un moment dat un singur copil se ridică de pe scaun şi pleacă. Atunci, cât timp în dreptul scaunului liber nu există un copil, toţi copiii aflaţi în aşteptare se mişcă în sens invers mişcării acelor ceasornicului, câte o poziţie, până când unul din ei ocupă locul liber.

Condiţii:

• la început toate scaunele sunt ocupate;
• fiecare copil aflat în aşteptare se află iniţial în dreptul unui scaun ocupat;
• când un copil avansează cu $n$ poziţii spre un loc pe scaun, toţi cei care aşteaptă avansează tot cu $n$ poziţii. Deoarece mişcarea este circulară, avansarea cu $4$ poziţii de la poziţia $18$, semnifică o deplasare în dreptul poziţiei $2$.

Cerință

Dacă se dă o secvenţă a numerelor de ordine a copiilor care pleacă la fiecare moment, să se scrie un program care să afişeze numărul scaunului pe care s-a aşezat fiecare copil care aşteaptă, dacă acest lucru este posibil.

Date de intrare

Pe prima linie a fişierului de intrare scaune.in se află două numere, separate prin spaţiu, reprezentând numărul de scaune $ns$ şi, respectiv, numărul copiilor care stau în aşteptare $nc$.

Pe următoarele $nc$ linii vor fi date poziţiile copiilor aflaţi în aşteptare.

În continuare până la sfârşitul fişierului sunt linii ce descriu numerele de ordine ale copiilor care se ridică unul câte unul de pe scaune şi părăsesc jocul.

Date de ieșire

Fişierul de ieşire scaune.out conţine $nc$ linii, fiecare linie conţinând poziţia iniţială de aşteptare a copilului şi poziţia ocupată, separate printr-un spaţiu. Liniile de ieşire trebuie să fie în aceeaşi ordine ca cele din fişierul de intrare.

În cazul în care un copil nu are nicio posibilitate să se aşeze, în dreptul său se va scrie 0 în fişierul de ieşire.

Restricții și precizări

• $1 \leq ns \leq 200$
• $nc \leq ns$

Exemplu

scaune.in

20 5
6
19
17
13
1
1
3
20
16

scaune.out

6 16
19 3
17 0
13 20
1 1