Federaţia Română Olimpică (FRO) încearcă să reconstituie istoria concursurilor şi olimpiadelor la care ţara noastră a participat. Pentru început încearcă să reconstituie pentru fiecare an numărul total de medalii câştigate.
Cum la întoarcerea de la fiecare concurs presa doreşte să ştie câte medalii au fost obţinute şi cât de bun este rezultatul obţinut faţă de anii precedenţi,  FRO vă solicită să scrieţi un program care să analizeze afirmaţii de tipul "Anul X a fost cel mai bun an începând din anul Y". Evident, prin "cel mai bun an" se înţelege anul în care au fost câştigate cele mai multe medalii.
La o astfel de afirmaţie programul vostru trebuie să răspundă cu DA, NU sau POATE.
Răspunsul este DA dacă:

1. este cunoscut numărul de medalii pentru fiecare an dintre X şi Y (inclusiv X şi Y).
2. numărul de medalii câştigate în anul X este <= decât numărul de medalii câştigate în anul Y.
3. pentru orice an Z, Y<Z<X, numărul de medalii câştigate în anul Z este < decât numărul de medalii câştigate în anul X.

Răspunsul este POATE dacă există în intervalul [Y,X] ani pentru care numărul de medalii nu este cunoscut, dar există cel puţin un set de valori ce ar putea fi atribuite anilor respectivi astfel încât răspunsul pentru acel set să fie DA.
În orice altă situaţie, răspunsul este NU.

Cerinţă

Scrieţi programul de care are nevoie FRO!

Date de intrare

Fişierul de intrare medalii.in conţine pe prima linie numărul natural n reprezentând numărul de ani pentru care FRO a reuşit să reconstituie informaţii (numărul de medalii câştigate). Pe următoarele n linii sunt descrise informaţiile reconstituite. Pe linia i dintre acestea se află două numere întregi separate prin spaţiu an_i nr_i cu semnficiaţia că în anul an_i au fost obţinute nr_i medalii. Anii sunt specificaţi cronologic (adică an_i<an_i+1, pentru orice 1<=i<n). Pe următoarea linie (linia n+2) se află un număr natural m reprezentând numărul de afirmaţii de analizat. Pe următoarele m linii sunt descrise cele m afirmaţii, câte o afirmaţie pe o linie. Linia ce descrie o afirmaţie conţine două numere întregi separate prin spaţiu Y X (Y<X) indicând cei doi ani din afirmaţie. 

Date de ieşire

Fişierul de ieşire medalii.out va conţine m linii, linia i dintre cele m conţinând răspunsul pentru afirmaţia i (DA NU sau POATE).

Restricţii

• 1 <= n <= 50000
• −10⁹  <= an_i  <= 10⁹ pentru 1<=i<=n
• 1  <=nr_i  <= 10⁹ pentru 1<=i<=n
• 1  <= m  <= 10000
• −10⁹ <= Y < X <= 10⁹

Exemple

medalii.in	medalii.out	medalii.in	medalii.out
4 2002 49 2003 59 2004 28 2005 38 2 2002 2005 2003 2005	NU DA	3 1985 57 1995 30 2005 60 3 1985 2005 2005 2015 1985 1995	NU POATE POATE

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com