회사 파티

Yankovich는 온라인 파티를 운영하는 POI라는 회사에서 소프트웨어 엔지니어로 일한다. 시스템을 시험하기 위해 직원들은 몇 가지 제약을 두고 파티를 열고 동료를 초대했다.

회사에는 계층 구조가 있다. 사장을 제외한 모든 직원에게는 직속 상사가 하나씩 있고, 상사 관계에 순환은 없다. 회사의 승진 절차 때문에 직원의 나이는 직속 상사의 나이보다 클 수 없다.

M개의 파티가 열린다. j번째 파티에는 주최자와 나이 구간 [Lj, Rj]가 있다. j번째 파티에는 아래 조건을 모두 만족하는 사람을 최대한 많이 초대한다.

• 주최자는 파티에 참석한다. 따라서 j번째 파티 주최자의 나이는 [Lj, Rj]에 있다.
• 초대받은 모든 사람의 나이는 [Lj, Rj]에 있어야 한다.
• 주최자를 제외한 초대받은 모든 사람은 파티에 참석하는 다른 직원과 직접 일해야 한다. 즉, 그 직원의 상사이거나 부하이다.
• Yankovich는 사용자가 참석한 파티 정보를 제공하는 프로그램을 맡고 있다. 첫 작업으로 그는 각 직원이 참석한 파티 수를 계산해야 한다. 그는 제출이 늦어서 이 프로그램을 작성할 도움을 청했다.

입력은 여러 줄로 이루어진다. 첫째 줄에는 직원 수와 테스트 파티 수를 나타내는 두 정수 N과 M (1 ≤ N, M ≤ 105)이 주어진다.

다음 N개 줄에는 회사의 계층 구조가 주어진다. 이 중 i번째 줄에는 i번째 직원의 나이와 직속 상사를 나타내는 두 정수 Ai와 Bi (1 ≤ Ai ≤ 105, 1 ≤ Bi ≤ N)가 주어진다. 직원은 1번부터 N번까지 번호가 매겨지며, 1번은 사장이다. 사장은 Bi = i인 유일한 직원이다. 모든 1 ≤ i ≤ N에 대해 Ai ≤ ABi임이 보장된다.

다음 M개 줄에는 테스트 파티의 데이터가 주어진다. 이 중 j번째 줄에는 파티 주최자와 문제에서 설명한 나이 구간의 경곗값을 나타내는 세 정수 Oj, Lj, Rj (1 ≤ Lj ≤ AOj ≤ Rj ≤ 105)가 주어진다.

N개의 정수를 공백 하나로 구분해 한 줄에 출력한다. i번째 수는 직원 i가 참석한 파티의 수여야 한다.