음악 추천

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

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

추천은 다음 순서로 진행된다. 사용 패턴 분석으로 트리의 노드 하나와 가중치가 정해진다. 선택된 노드를 루트로 하는 서브트리의 모든 노드가 추천 대상이 된다. 이 서브트리의 노드에는 가중치에 따른 점수가 고르게 나뉘어 부여된다. 가중치가 노드 수로 나누어떨어지지 않으면 몫만 분배한다. 아래 그림에서는 노드 하나가 선택되고 가중치 23이 주어졌다. 서브트리의 노드는 다섯 개이고 23을 5로 나누면 몫이 4, 나머지가 3이므로 각 노드에 4점이 부여된다. 점수가 높을수록 추천될 확률이 높아진다.

특정 가수의 곡만 계속 추천되는 상황을 막기 위해 가수별 평균 점수를 관리하려고 한다. 위 트리에서 빨간 벽돌 무늬 노드가 아이유의 곡이라고 하자. 그림처럼 서브트리가 선택되면 빨간 노드가 두 개이므로 각 노드에 4점씩 부여되어 아이유 곡의 점수 합은 8이 된다. 트리 전체에서 빨간 노드는 세 개이므로 아이유 곡의 평균 점수는 $8/3$점이 된다.

이처럼 노드와 가중치를 고르는 과정이 반복될 때, 가수별 평균 점수가 주어진 목표 점수를 넘는 시점을 구하려고 한다. 트리의 형태와 추천 결과 데이터가 주어지면, 노드마다 해당 곡을 부른 가수의 평균 점수가 목표 점수를 넘는 시점을 계산하는 프로그램을 작성하시오.

첫째 줄에 세 정수가 주어진다. 곡의 수 $N$($2 \le N \le 100{,}000$), 추천 알고리즘 결과 데이터의 수 $K$($1 \le K \le 100{,}000$), 목표 점수 $J$($10 \le J \le 10^8$)이다. 곡은 1번부터 $N$번까지 번호가 붙어 있다. 둘째 줄에는 2번 곡부터 차례로 각 곡의 부모 곡 번호가 $N-1$개 주어진다. 1번 곡은 부모가 없다. 셋째 줄에는 1번 곡부터 $N$번 곡을 부른 가수의 번호가 $N$개 주어진다. 가수 번호는 1 이상 $N$ 이하의 자연수이다. 다음 $K$개의 줄에 결과 데이터가 하나씩 주어진다. 각 데이터는 $T$, $P$, $S$ 세 값이다. $T$는 데이터가 계산된 시간으로 1 이상 $10^9$ 이하의 자연수이다. $P$는 점수를 부여할 서브트리의 루트 곡 번호이다. $S$는 서브트리에 부여할 가중치로 1 이상 $10^9$ 이하의 자연수이다.

$N$개의 줄을 출력한다. 1번 곡부터 차례로, 그 곡을 부른 가수의 평균 점수가 $J$를 넘는 시간을 출력한다. 넘는 일이 없으면 -1을 출력한다. 같은 가수가 부른 곡은 같은 값을 가진다.