Rezolvare PBinfo #3219

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 1 x 1. 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ța

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 de ieșire 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 și precizări

• 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.

Exemplu:

colina.in

6 5
1 5 9 7 2 1
5 6 1 9 4

colina.out

DA 2
NU
DA 1 6
DA 3
NU