Mūsdienu elektroniskajām iekārtām ir nepieciešama regulāra uzlāde, kas parasti tiek veikta, izmantojot dažādu izmēru adapterus. Šajā uzdevumā interesēsimies par adapteru ieslēgšanu kontaktligzdu blokā, kur kontaktligzdas izvietotas vienā rindā (1. attēlā (a) parādīts sešu kontaktligzdu bloks). Katra adaptera kontaktdakšiņa ir novietota tā, ka, ieslēdzot to kontaktligzdā, adaptera garākā mala būs paralēla kontaktligzdu bloka garākajai malai, turklāt kontaktligzdā adapteru var ieslēgt divos variantos – viens variants no otra atšķiras ar pagriešanu par $180$ grādiem. Pieņemsim, ka katra adaptera garākās malas garums ir kontaktligzdu augstuma daudzkārtnis.

Piemēram, ja adapters (skat. 2. att. (a) un (b)) ir divas vienības augsts, tad to var ieslēgt iepriekš aplūkotā kontaktligzdu bloka ceturtajā kontaktligzdā divos variantos – pēc ieslēgšanas tajā bez tās, kurā tiek iesprausta kontaktdakšiņa (attēlos apzīmēta ar "x"), tiks aizsegta attiecīgi piektā (1. att. (b)) vai trešā (1. att. (c)) kontaktligzda. Labā ziņa ir tā, ka adaptera korpuss var iet arī ārpus kontaktligzdu bloka (1. att. (d)), aizsedzot pēc iespējas mazāk vai nemaz neaizsedzot liekas kontaktligzdas. Ņemot to vērā, šajā piemērā sešu kontaktligzdu blokā varētu ieslēgt, augstākais, četrus šāda izmēra adapterus (skat. 1. att. (e)).

Katru adapteru raksturo tā garums $l_i$ un kontaktdakšiņas atrašanās pozīcija adaptera korpusā $p_i$ ($1 \leq p_i \leq l_i$). 2. attēlā (attiecīgi, (a), (b), (c) un (d)) redzami attiecīgi adapteri $(2;1)$, $(2;2)$, $(3;2)$ un $(4;3)$.

Saprotams, ka kontaktligzdu blokā vienlaicīgi ieslēgto adapteru skaits ir atkarīgs no adapteru izmēriem. Ja visi adapteri ir trīs vienības gari un kontaktdakšiņa atrodas otrajā (vidējā) pozīcijā (skat. 2. att. (c)), tad sešu kontaktligzdu blokā varēs ieslēgt ne vairāk kā divus šādus adapterus (piemēram, ieslēdzot tos trešajā un sestajā kontaktligzdā, skat. 1. att. (f)).

Uzrakstiet datorprogrammu, kas dotam kontaktligzdu skaitam blokā un dotajam adapteru komplektam nosaka, cik no tiem vienlaikus var ieslēgt kontaktligzdu blokā un kā tieši tie jāieslēdz!

Pirmajā rindā doti divi naturāli skaitļi -- kontaktligzdu skaits blokā $N$ ($N \leq 10^9$) un adapteru skaits $A$ ($A \leq 2 \times 10^5$).

Nākamajās $A$ rindās katrā dots viena adaptera apraksts -- divi naturāli skaitļi $l_i$ (adaptera garums, $1 \leq l_i \leq 10^9$) un kontaktdakšiņas atrašanās pozīcija adaptera korpusā $p_i$ ($1 \leq p_i \leq l_i$).

Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddatu pirmajā rindā jābūt naturālam skaitlim $M$ -- lielākajam adapteru, kurus no dotajiem var vienlaikus ieslēgt dotajā kontaktligzdu blokā.

Nākamajās $A$ rindās katrā jābūt veselam skaitlim robežās no $-N$ līdz $N$. Katram $i$ ($1 \leq i \leq A$) izvaddatu $i+1$-ajā rindā jābūt raksturotam, kā kontaktligzdu blokā jāieslēdz adapters, kurš ievaddatos dots kā $i$-tais pēc kārtas.

Šim skaitlim jābūt:

• $0$, ja attiecīgais adapters nav ieslēgts kontaktligzdā;
• $v$ ($1 \leq v \leq N$), ja attiecīgais adapters ir ieslēgts kontaktligzdā, orientējot adapteru tā, kā dots ievaddatos;
• $-v$ ($1 \leq v \leq N$), ja attiecīgais adapters ir ieslēgts kontaktligzdā, orientējot adapteru pagrieztu par $180$ grādiem attiecībā pret to, kā dots ievaddatos.

Nenulles skaitļu kopskaitam jābūt $M$ un blokā ieslēgto adapteru konfigurācijai jābūt neprerunīgai. Ja iespējamas vairākas derīgas adapteru konfigurācijas ar lielāko $M$ vērtību, izvadiet informāciju par jebkuru no tām.