The Company Choir

Byteasar runs the in-house choir at his company. Unfortunately, he is often short of singers, because every so often a group of choir members quits and moves abroad, so he constantly has to look for new people willing to sing.

The company where Byteasar works has a very tidy organizational structure: every employee except the boss has exactly one direct supervisor. When looking for new choir members, Byteasar asks a chosen employee to prepare a list of the best-singing people among that employee's subordinates. He also requires that the voice pitch of everyone on the list fall within a given range.

Here, the "subordinates" of an employee are all employees below them in the hierarchy (directly or indirectly), and do not include the employee themselves.

Write a program that:

• reads the description of the company and the list of questions from standard input,
• determines the answer to each question,
• writes the result to standard output.

The first line contains two integers $n$ and $q$ ($1 \le n \le 100000$, $1 \le q \le 20000$): the number of employees and the number of questions.

Each of the next $n$ lines contains three integers $p_i$, $w_i$, and $s_i$ ($0 \le p_i \le n$, $0 \le w_i, s_i \le 1000000000$). Here $p_i$ is the supervisor of employee $i$ ($0$ means this employee is the boss), $w_i$ is their voice pitch, and $s_i$ is their singing ability (the higher the value, the better they sing). There is exactly one boss, and all employees have distinct singing abilities $s_i$.

Each of the next $q$ lines contains four integers $t_i$, $a_i$, $b_i$, and $k_i$ ($1 \le t_i \le n$, $0 \le a_i \le b_i \le 1000000000$, $1 \le k_i \le 1000000$). This is a request for the $k_i$ best-singing employees among the subordinates of employee $t_i$ whose voice pitch lies in the range $[a_i, b_i]$. The sum of all $k_i$ does not exceed $100000$.

Print $q$ lines, one answer per question.

The answer to the $i$-th question lists the numbers of the matching subordinates, from the highest singing ability to the lowest, separated by single spaces on one line. If fewer than $k_i$ subordinates satisfy the condition, print all of their numbers and then append a single $0$.