8514번 - Biuro 다국어

Bajteusz jest kierownikiem wewnątrzzakładowego chóru w swojej firmie. Niestety, często brakuje mu ochotników do śpiewu, gdyż co jakiś czas grupa chórzystów rzuca pracę i emigruje do Wielkiej Bajtanii. Z tego powodu musi wciąż na nowo szukać chętnych do śpiewu.

Firma, w której pracuje Bajteusz ma bardzo uporządkowaną strukturę organizacyjną. Każdy pracownik (poza szefem) posiada dokładnie jednego bezpośredniego przełożonego. Bajteusz szukając nowych chórzystów prosi pewnego pracownika by stworzył mu listę najlepiej śpiewających pracowników spośród jego podwładnych. Dodatkowo, Bajteusz wymaga by wysokość głosu pracowników na stworzonej liście mieściła się w określonym przedziale. Zazwyczaj bardzo długo musiał czekać na otrzymanie gotowej listy, dlatego poprosił Ciebie o pomoc w napisaniu programu, który usprawni ten proces.

Napisz program, który:

• wczyta ze standardowego wejścia opis firmy, w której pracuje Bajteusz oraz listę pytań,
• wyznaczy odpowiedzi na poszczególne pytania,
• wypisze wynik na standardowe wyjście.

W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite n i q (1 ≤ n ≤ 100000,1 ≤ q ≤ 20000), oznaczające odpowiednio liczbę pracowników firmy oraz ilość pytań Bajteusza. Każda z kolejnych n linii zawiera po trzy liczby całkowite p_i, w_i oraz s_i (0 ≤ p_i ≤ n, 0 ≤ w_i,s_i ≤ 1000000000). Pierwsza z nich oznacza numer przełożonego i-tego pracownika (0 oznacza, że ten pracownik jest szefem firmy), druga to jego wysokość głosu, zaś trzecia oznacza jego umiejętność śpiewania (im wyższa, tym lepiej śpiewa dany pracownik). W firmie istnieje dokładnie jeden szef oraz wszyscy pracownicy mają różne umiejętności śpiewania.

W kolejnych q liniach znajdują się opisy pytań Bajteusza. Każdy z nich składa się z czterech liczb całkowitych t_i, a_i, b_i i k_i (1 ≤ t_i ≤ n,0 ≤ a_i ≤ b_i ≤ 1000000000,1 ≤ k_i ≤ 1000000). Oznaczają one prośbę Bajteusza skierowaną do pracownika numer t_i o stworzenie listy k_i najlepiej śpiewających pracowników spośród jego podwładnych o wysokości głosu w przedziale [a_i, b_i]. Suma wszystkich k_i nie przekracza 100000.

Na standardowe wyjście należy wypisać q linii - odpowiedzi na kolejne pytania. Odpowiedzią na i-te pytanie jest lista k_i numerów pracowników posortowana od największej do najmniejszej umiejętności śpiewania. Jeśli podany pracownik posiada mniej niż k_i podwładnych o pożądanej wysokości głosu, należy wypisać ich wszystkie numery oraz jedno zero.