{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYankovich 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.\u003c/p\u003e\u003cp\u003eThe 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\u0027s promotion processes, the age of an employee is not greater than the age of his direct manager.\u003c/p\u003e\u003cp\u003eThese initial parties work in the following way: \u003c/p\u003e\u003cul\u003e \u003cli\u003e Each party $$$j$$$ has an owner $$$O_j$$$ and an age range, from $$$L_j$$$ to $$$R_j$$$ . \u003c/li\u003e\u003cli\u003e 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. \u003c/li\u003e\u003cli\u003e 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. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYankovich 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eIn 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.\u003c/p\u003e\u003cp\u003eThe 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 \u003d i$$$). It is guaranteed that $$$A_i \\le A_{B_i}$$$.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput 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.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 3\n8 1\n3 5\n5 1\n2 3\n4 1\n3 3\n1 2\n7 1\n2 2\n3 2\n3 5 9\n5 3 8\n3 2 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 3 1 1 2 0 2 0 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}