사내 합창단

바이트아사르는 회사 안에서 합창단을 이끄는 단장이다. 하지만 단원 중 일부가 이따금 회사를 그만두고 다른 나라로 떠나 버려서, 노래할 사람이 늘 부족하다. 그래서 그는 새 단원을 끊임없이 찾아야 한다.

바이트아사르가 다니는 회사는 조직 구조가 매우 잘 정리되어 있다. 사장을 제외한 모든 직원은 직속 상사를 정확히 한 명씩 가진다. 새 단원을 찾을 때, 바이트아사르는 어떤 직원에게 그 직원의 부하 직원들 중에서 노래를 가장 잘하는 사람들의 명단을 만들어 달라고 부탁한다. 이때 명단에 오르는 직원의 목소리 높이가 특정 구간 안에 들어야 한다는 조건도 붙는다.

여기서 어떤 직원의 "부하 직원"이란 조직도에서 그 직원 아래에 있는 모든 직원(직속이든 아니든)을 뜻하며, 그 직원 자신은 포함하지 않는다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 회사의 구조와 질문 목록을 읽는다.
• 각 질문에 대한 답을 구한다.
• 결과를 표준 출력에 쓴다.

첫 번째 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \le n \le 100000$, $1 \le q \le 20000$). 각각 회사의 직원 수와 질문의 수를 나타낸다.

이어지는 $n$개의 줄에는 각각 세 정수 $p_i$, $w_i$, $s_i$가 주어진다 ($0 \le p_i \le n$, $0 \le w_i, s_i \le 1000000000$). $p_i$는 $i$번 직원의 상사 번호이며, $0$이면 그 직원이 사장임을 뜻한다. $w_i$는 목소리 높이, $s_i$는 노래 실력이다(값이 클수록 노래를 잘한다). 사장은 정확히 한 명이고, 모든 직원의 노래 실력 $s_i$는 서로 다르다.

이어지는 $q$개의 줄에는 각각 네 정수 $t_i$, $a_i$, $b_i$, $k_i$가 주어진다 ($1 \le t_i \le n$, $0 \le a_i \le b_i \le 1000000000$, $1 \le k_i \le 1000000$). 이는 $t_i$번 직원의 부하 직원 중 목소리 높이가 구간 $[a_i, b_i]$에 속하는 사람들 가운데 노래를 가장 잘하는 $k_i$명의 명단을 요청하는 질문이다. 모든 $k_i$의 합은 $100000$을 넘지 않는다.

$q$개의 줄을 출력한다. 각 줄은 해당 질문에 대한 답이다.

$i$번째 질문의 답은 조건을 만족하는 부하 직원들의 번호를 노래 실력이 큰 순서대로 나열한 것이다. 한 줄에 번호들을 공백 하나로 구분하여 출력한다. 조건을 만족하는 부하 직원이 $k_i$명보다 적으면, 그들의 번호를 모두 출력한 뒤 마지막에 $0$ 하나를 덧붙인다.