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

Ca sef al Departamentului de Siguranta Nationala, sunteti insarcinat sa amplasati in fiecare din cele N locatii unul din cele doua tipuri de lansatoare de rachete.

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

• 0 ≤ N, L ≤ 1 000 000
• 0 ≤ 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?