Državno natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 2. zadatak - 2. dan

Z zbunjenih žaba zabunom se zateklo u zakutku zelene livade i žarko želi završiti na drugoj strani ceste. Za ovu priliku cesta se nalazi u standardnom koordinatnom sustavu (x koordinata raste prema desno, y koordinata raste prema gore), proteže se beskonačno s lijeva na desno te je široka točno 6 metara. Drugim riječima, cesta je područje ravnine omeđeno pravcima y=0 i y=6. Cesta je pravcem y=3 podjeljena na dvije trake jednake širine – točno 3 metra svaka.

Po cesti se kreću kamioni pravokutnog oblika proizvoljne duljine, široki točno 3 metra. Postavljeni su tako da u potpunosti svojom širinom zauzimaju jednu od traka. Kamioni u gornjoj traci kreću se prema lijevo, a kamioni u donjoj traci prema desno. Svi kamioni se kreću jednoliko pravocrtno brzinom od točno jednog metra u sekundi.

Za svaki od kamiona poznat je smjer njegovog kretanja te pozicija njegovog prednjeg kraja u vremenu 0. Prednji kraj kamiona koji se kreće prema lijevo je x koordinata njegovog lijevog ruba (i analogno desnog ruba za kamion koji se kreće prema desno).

Žabe su označene redom brojevima od 1 do Z. Žaba K se pojavi na donjem rubu ceste na koordinatama (XK, 0) u vremenu TK te odmah počinje prelaziti cestu krećući se ravno prema gore također jednoliko pravocrtno brzinom od jednog metra u sekundi.

Kažemo da je žabu pregazio kamion ukoliko se u bilo kojem trenutku žaba nađe strogo unutar pravokutnika koji opisuje kamion. Ako se žaba nađe na rubu pravokutnika onda ne smatramo da ju je taj kamion pregazio u tom trenutku.

Napišite program koji će, na temelju pozicija kamiona u vremenu 0, za svaku zadanu žabu odrediti da li je uspješno prešla cestu ili ju je pregazio neki od kamiona.

Napomena: Iako su početne pozicije kamiona i žaba zadane prirodnim brojevima, primijetite da se i kamioni i žabe kreću kontinuirano. Drugim riječima, za svaki realni broj T, u vremenu T se svaka žaba i svaki kamion pomakne za točno T metara u smjeru u kojem se kreću.

ULAZNI PODACI

U prvom redu nalaze se dva prirodna broja N i Z (1 ≤ N, Z ≤ 100 000), broj kamiona i broj žaba. U svakom od sljedećih N redova nalazi se znak SK koji označava smjer kretanja (‘L’ za lijevo i ‘D’ za desno) te dva cijela broja XK i LK (0 ≤ XK, ≤ 108 , 1 ≤ LK ≤ 108 ), pozicija prednjeg kraja u vremenu 0 te duljina odgovarajućeg kamiona u metrima.

Slijedi Z redova koji opisuju žabe: u svakom retku po dva prirodna broja TK i XK (0 ≤ TK, XK ≤ 108 ), vrijeme u kojem žaba K počinje prelaziti cestu te njezina početna pozicija.

Nijedna dva kamiona neće se preklapati, ali se mogu dodirivati. Dozvoljeno je da se dvije žabe nalaze u istoj poziciji u istom vremenu.

IZLAZNI PODACI

Potrebno je ispisati Z redova, po jedan za svaku žabu onim redom koji su dane u ulazu. Ako će žaba uspješno preći cestu potrebno je u odgovarajući red ispisati 'DA', a u suprotnom potrebno je ispisati 'NE'.

PRIMJERI TEST PODATAKA

ulaz

4 6
D 3 2
L 0 2
L 8 1
D 5 1
0 1
0 1
0 7
0 8
3 2
4 2

izlaz

DA
DA
NE
DA
NE
DA

ulaz

3 4
D 7 4
D 8 1
D 12 1
0 7
0 11
0 12
1 11

izlaz

NE
DA
NE
NE

ulaz

2 3
D 3 3
L 12 3
0 5
0 6
0 7

izlaz

NE
DA
NE