O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de forma unei fâşii de dimensiune 1×N, fiind apoi împărţit în parcele de dimensiune 1x1. Pe fiecare dintre cele N parcele de dimensiune 1×1 firma poate construi câte o casă, dacă există clienţi interesaţi.
Terenul este amplasat pe una dintre cele şapte coline ale unui oraş vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la 1 la N, altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziţie, unde se atinge altitudinea maximă a acestui teren, iar pentru poziţiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu h1, h2, ..., hN altitudinile parcelelor, există un indice vf, 1≤vf≤N, astfel încât h1<h2<...hvf-1<hvf>hvf+1>...>hN.
Clienţii au înregistrat deja cereri de construcţie pentru M case. Fiecare dintre aceste cereri specifică însă o restricţie mai ciudată, şi anume faptul că doresc ca parcela de construcţie să se afle exact la altitudinea qj (1≤j≤M).
Cerinţă
Scrieţi un program care determină pentru fiecare cerere j (1≤j≤M) dacă firma poate îndeplini restricţia respectivă, mai exact dacă există măcar o parcelă i (1≤i≤N) pentru care hi=qj.
Date de intrare
Fişierul de intrare colina.in conţine pe prima linie două numere naturale N şi M ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc N numere naturale h1 h2 ... hN, reprezentând altitudinile parcelelor. Pe ultima linie se găsesc M numere naturale q1 q2 ... qM, reprezentând altitudinile din cererile clienţilor. Numerele aflate pe aceeaşi linie sunt separate prin spaţii.
Date de ieşire
Fişierul colina.out va conţine M linii. Pe linia j (1≤j≤M) va fi scris mesajul NU, dacă nu este posibilă construirea unei case la altitudinea qj. În caz contrar, pe linia j va fi scris mesajul DA, urmat de un spaţiu, apoi de indicii i pentru care hi=qj, separaţi de asemenea prin câte spaţiu şi scrişi în ordine crescătoare.
Restricţii
• 1 ≤ N, M ≤ 100 000
• 0 < hi, qj < 231 pentru orice 1≤i≤N şi 1≤j≤M
• Valorile qj sunt distincte (nu s-au acceptat cereri identice).
• Pentru teste în valoare de 20 puncte: N×M ≤ 100 000
• Pentru teste în valoare de 40 puncte: hmax ≤ 100 000 unde hmax este altitudinea maximă a parcelelor.