시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 512 MB 140 47 22 23.158%

문제

멜론은 국내 최다 고객과 음원을 보유한 디지털 뮤직 플랫폼이다. 멜론의 특징 중 하나는 사용자 개인별 맞춤 큐레이션 서비스로, 사용자의 취향 및 콘텐츠의 특성을 분석하여 좋아할 만한 음악을 추천함으로써 사용자가 계속해서 쓸 수 있는 서비스를 만드는 것이다. 사용자가 만족할 만한 서비스를 제공하기 위해서는 추천 알고리즘의 성능을 우수하게 유지하는 것이 중요하기 때문에, 사용자의 피드백에 따라 추천 알고리즘을 개선하거나, 좋은 성능을 보일 수 있는 새로운 추천 알고리즘을 고안하는 과정이 필요하다.

프로도는 사용자가 좋아할 만한 음악을 추천하기 위한 새로운 추천 알고리즘을 고안했다. 이 알고리즘은 음악 간 유사도를 트리의 형태로 만든 뒤 사용자의 입력에 따라 추천할 음악을 결정하는 방식이다. 예를 들어, 음악 간 유사도를 표현한 다음 트리를 살펴보자. 여기에서 각각의 노드가 곡을 나타내며, 노드의 색깔은 가수를 의미한다.

추천이 이루어지는 과정은 다음과 같다. 사용 패턴 분석을 통해 트리에 있는 노드 중 하나와 가중치가 결정되는데, 선택된 노드가 루트가 되는 서브트리의 모든 노드가 추천 대상이 된다. 이 서브트리에 속한 노드에 가중치에 따른 점수가 고르게 부여된다. 가중치가 노드의 수로 나누어떨어지지 않는 경우 몫만이 분배된다. 예를 들어, 아래 그림에서처럼 노드가 하나 선택되고 여기에 가중치 23을 부여한다고 가정해보자. 이 서브트리에 속한 노드는 총 다섯 개이고, 23을 5로 나누면 몫이 4가 되고 나머지가 3이 되기 때문에 각각의 노드에 점수 4가 부여된다. 이 점수가 높을수록 추천에서 선택될 확률이 높아진다.

이때, 특정한 가수의 곡만 추천되는 상황을 방지하기 위해 가수 별로 평균 점수를 관리하려고 한다. 위 트리에서 빨간색 벽돌 무늬로 표시된 노드가 아이유의 곡이라고 가정하자. 위의 그림과 같이 서브트리가 선택된 상황의 경우, 빨간색 노드가 총 두 개이므로 노드 하나당 4점씩 부여되어 아이유의 곡의 점수의 합은 8이 된다. 트리에서 빨간색으로 표시된 노드가 총 세 개이므로, 아이유의 곡은 평균 8/3점이 된다.

위와 같이 트리의 노드와 가중치가 선택되는 과정이 반복된다고 할 때, 가수 별 평균 점수가 주어진 목표 점수를 언제 초과하게 되는지 계산하려고 한다. 트리의 형태와 추천 알고리즘의 결과 데이터가 입력으로 주어질 때, 노드 별로 가수의 평균 점수가 목표 점수를 초과하는 시점을 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 세 정수로, 곡의 수 N(2 ≤ N ≤ 100,000), 추천 알고리즘의 결과 데이터의 수 K(1 ≤ K ≤ 100,000), 목표 점수 J(10 ≤ J ≤ 108)가 주어진다. 각각의 곡은 1번부터 N번까지 번호가 붙어 있다. 다음 줄에 N-1개의 곡 번호가 주어지는데, 이는 2번 곡부터 해당 곡의 부모 노드가 되는 곡의 번호이다. 1번 곡은 부모 노드가 없다. 다음 줄에 N개의 수가 주어지는데, 이는 1번 곡부터 해당 곡을 부른 가수의 번호이다. 가수의 번호는 1 이상 N 이하의 자연수이다. 다음 K개의 줄에 추천 알고리즘의 결과 데이터가 하나씩 주어진다. 결과 데이터는 T, P, S의 세 값으로 주어진다. T는 데이터가 계산된 시간으로, 1 이상 109 이하의 자연수이다. P는 점수가 부여되는 서브트리의 루트가 되는 곡의 번호이다. S는 서브트리에 부여할 가중치로, 1 이상 109 이하의 자연수이다.

출력

출력은 N개의 줄로 이루어진다. 1번 곡부터 해당 곡을 부른 가수의 평균 점수가 J를 넘게 되는 시간을 출력한다. 점수가 J를 넘는 일이 없는 경우 -1을 출력한다. 같은 가수가 부른 곡은 같은 값을 가지게 될 것이다.

예제 입력 1

3 3 52
1 1
1 1 3
1 1 90
2 2 100
3 1 30

예제 출력 1

2
2
-1