Fişierul intrare/ieşire:	sn.in, sn.out	Sursă	Winter Challenge 2008, Runda 2
Autor	Bogdan Alexandru Stoica	Adăugată de	Bogdan-Alexandru Stoica •fireatmyself
Timp execuţie pe test	0.475 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Siguranta Nationala

Pentru ca a fost batut de prea multe ori la 'Jocul pe grid' de catre Presedinte, Primul Ministru planuieste o lovitura de stat. Din fericire, Dubluveu, a fost informat la timp de intentiile Sefului Guvernului si are de gand sa-si organizeze o aparare temeinica. Palatul Prezidential este plasat strategic, neputandu-se ajunge la acesta decat pe o singura sosea de lungime L kilometrii. Pe marginea sa Dubluveu cere amplasarea, in N locatii fixe, a doua tipuri de dispozitive: lansatoare de rachete sol-sol si lansatoare de rachete sol-aer (cate un tip in fiecare locatie). Daca un dispozitiv (nu conteaza de ce tip) este plasat in locatia i, acesta va putea distruge orice forma de viata doar intr-un interval [a_i,b_i]. Pentru a fi sigur ca Primul Ministru nu v-a putea ajunge la el, Dubluveu vrea ca fiecare punct al soselei sa fie pazit de ambele tipuri de dispozitive.

Cerinta

In Secretar General al Consiliul Suprem de Aparare a Tarii, trebuie sa dispuneti amplasarea a cate unui tip de lansator de rachete in fiecare din cele N locatii.

Date de intrare

Pe prima linie a fisierului de intrare sn.in se afla doua numere L si N. Pe urmatoarele N linii se afla doua numere a_i, b_i, cu seminifcatia ca un dispozitiv plasat in locatia i va putea distruge orice forma de viata ce se afla in intervalul [a_i,b_i].

Date de iesire

Fisierul de iesire sn.out va contine N linii, pe linia i se va indica tipul de lansator de racheta amplasat in respectiva locatie ('sol-sol' daca in i se amplaseaza un lansator de rachete sol-sol, respectiv 'sol-aer' in celalalt caz). Se garanteaza ca pentru datele de test va exista intotdeauna solutie.

Restrictii

• 1 ≤ N, L ≤ 1 000 000
• 1 ≤ a_i ≤ b_i ≤ L
• intervalele vor fi date in ordinea crescatoare a lui a_i si, in caz de egalitate, in ordinea crescatoare a lui b_i
• fiecare punct este continut de cel putin un interval din fisierul de intrare
• intr-o locatie poate fi amplasat doar un singur tip de lansator de rachete
• !ATENTIE! din cauza volumului mare de date din fisierul de intrare este recomandata citirea cu gets sau fgets

Exemplu

Cum se trimit solutii?