U gradu Luminiji održava se veliki noćni festival svjetla. Oko glavnog trga postavljen je kružni niz od \(m\) stupova za lampice, numeriranih od \(1\) do \(m\). Budući da su postavljeni u krug, stupovi \(1\) i \(m\) su susjedni.

Svaki stup pripada jednoj od \(n\) udruga koje sudjeluju na festivalu. Svaka udruga želi da njezini stupovi zasvijetle određenim ukupnim intenzitetom svjetla prije nego što se povuče iz natjecanja.

Tijekom večeri gradonačelnik najavljuje \(k\) rundi pojačavanja svjetla. U svakoj rundi pojača se svjetlo na određenom uzastopnom dijelu stupova (moguće i preko kraja kruga), a svaki zahvaćeni stup dobije dodatnu količinu svjetlosne energije.

Tvoj je zadatak odrediti, za svaku udrugu, nakon koje runde će ukupna svjetlosna energija na svim njezinim stupovima dosegnuti ili premašiti zadani cilj. Ako ni nakon svih rundi cilj nije dosegnut, ispiši "NE".

Ulazni podatci

U prvom retku nalaze se dva cijela broja \(n\) i \(m\) (\(1 \leq n, m \leq 300000\)) — broj udruga i broj stupova.

U drugom retku nalazi se \(m\) cijelih brojeva \(o_i\) (\(1 \leq o_i \leq n\)) — gdje \(o_i\) označava kojoj udruzi pripada i-ti stup.

U trećem retku nalazi se \(n\) cijelih brojeva \(p_i\) (\(1 \leq p_i \leq 10^9\)) — gdje \(p_i\) označava koliko ukupne svjetlosne energije želi prikupiti i-ta udruga.

U četvrtom retku nalazi se cijeli broj \(k\) (\(1 \leq k \leq 300000\)) — broj rundi pojačavanja svjetla.

U sljedećih \(k\) redaka nalaze se po tri cijela broja \(l_i\), \(r_i\), \(a_i\):

• Ako je \(l_i \leq r_i\), pojačavanje zahvaća stupove \(l_i, l_i+1, ..., r_i\).
• Ako je \(l_i > r_i\), pojačavanje zahvaća stupove \(l_i, ..., m, 1, ..., r_i\) (prelazi kraj kruga).

Svaki zahvaćeni stup dobiva dodatnih \(a_i\) jedinica svjetlosne energije (\(1 \leq a_i \leq 10^9\)).

Izlazni podatci

Ispišite \(n\) redaka.

U i-tom retku ispišite:

• broj runde nakon koje i-ta udruga prvi put skupi barem \(p_i\) jedinica energije, ili
• "NE" ako ni nakon svih \(k\) rundi ne uspije skupiti dovoljno energije.

Podzadatci

Ulaz primjera

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

Izlaz primjera

3
NE
1