407626: GYM102861 E Party Company

Yankovich works as Software Engineer in a company called POI (Party Online Infinitely), as the name suggests it is a company that promotes online parties. To test the systems some employees threw parties and invited only the company employees with some restrictions.

The company employees form a hierarchical structure, where each one has a direct manager (except the company owner), and has no cyclic relations. Due to the company's promotion processes, the age of an employee is not greater than the age of his direct manager.

These initial parties work in the following way:

• Each party $$$j$$$ has an owner $$$O_j$$$ and an age range, from $$$L_j$$$ to $$$R_j$$$ .
• To be invited to a party an employee needs to have age inside the age range $$$[L_j, R_j]$$$ of the party. It is guaranteed that the age of the owner of each party is inside the age range of their parties.
• Besides the age restriction, to be invited to a party an employee must work directly with another employee that will be invited (as direct manager or direct subordinate), except for the party owner.

Yankovich is responsible for the application that computes data about the parties a user has participated. As an initial task he has to calculate how many parties an employee was invited to. Since he is late to deliver his first task, help him calculating this information for these initial parties.

In the first line there are two integers $$$N, M$$$ $$$(1 \le N, M \le 10^5)$$$ representing the number of employees and the number of initial parties, respectively.

The next $$$N$$$ lines contain the employee data. In the $$$i$$$-th of these lines there are two integers $$$A_i, B_i$$$ $$$(1 \le A_i ≤ 10^5, 1 \le B_i \le N)$$$ representing the age of $$$i$$$-th employee and his direct manager (the employees are numbered from 1 to $$$N$$$, the company owner is the number 1 and he is the unique employee that has $$$B_i = i$$$). It is guaranteed that $$$A_i \le A_{B_i}$$$.

The next $$$M$$$ lines define the initial parties. In the $$$j$$$-th of these lines there are three integers $$$O_j, L_j, R_j$$$ $$$(1 \le L_j \le A_{O_j} \le R_j \le 10^5)$$$ representing the owner of this party, and its age range.

Output one single line containing $$$N$$$ integers (separated by a single space). The $$$i$$$-th of these numbers should be the number of parties the employee number $$$i$$$ was invited to.

10 3
8 1
3 5
5 1
2 3
4 1
3 3
1 2
7 1
2 2
3 2
3 5 9
5 3 8
3 2 6

2 1 3 1 1 2 0 2 0 1