대안 블록체인 알고리즘

은행 사기를 줄이기 위해 금융문제위원회(FPC)는 현대적인 은행 위원회이므로 블록체인을 사용하기로 했다. 계좌마다 그 계좌에 적용된 모든 거래를 담은 블록체인을 유지한다.

FPC는 암호화와 작업 증명(proof of work)이 번거롭고 가치가 없다고 판단했다. 그래서 각 블록에는 어느 블록에서든 체인의 처음까지 거슬러 올라가는 데 필요한 최소한의 정보만 담는다. 그래도 사고는 일어나므로, 각 블록에는 체인의 연속성을 검증할 수 있도록 부모 노드를 가리키는 참조를 포함한다.

당신의 일은 블록체인을 검증하고 계좌의 잔액을 반환하는 것이다.

블록의 부모 id가 바로 앞 블록의 id와 일치하지 않으면 그 블록은 잘못된 것이다. 프로그램은 잔액이 음수가 될 수 있는 거래가 계좌에 있는지도 확인해야 한다.

첫 번째 블록(제네시스 블록)의 부모 id는 반드시 0이어야 한다.

첫 줄에 정수 $1 \leq N \leq 10^{6}$이 주어진다. 이는 체인에 있는 블록의 수이다.

이어서 $N$개의 줄에 각각 세 정수가 주어진다. 블록 id $1 \leq i \leq 10^{6}$, 부모 id $1 \leq p \leq 10^{6}$, 계좌로 입금되거나 계좌에서 출금되는 금액 $-10^{6} \leq m \leq 10^{6}$이다.

모든 거래는 정수의 언더플로나 오버플로를 일으키지 않는다고 가정할 수 있다. 블록 id는 모두 서로 다르다고 가정할 수 있다.

거래 후 계좌의 잔액이 0보다 작아지면 NO_MONEY를 출력한다. 블록이 잘못되었으면 INVALID를 출력한다. 그 외에는 계좌의 최종 잔액을 정수로 출력한다.