Alternative Blockchain Algorithms

Interview

Time limit1sMemory limit2048 MB

Summary

Walk the blocks in order, check each parent id against the previous block id, and print the final balance, NO_MONEY, or INVALID.

Level: Easy2 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Problem

To reduce fraud in banking, the Financial Problems Committee (FPC) chose to use a blockchain, since it is a modern banking committee. For every account, a blockchain records all the transactions applied to that account.

The FPC decided that encryption and proof of work are cumbersome and not worth the effort. Each block therefore contains only the essentials needed to trace back to the beginning of the chain from any block. Accidents still happen, so each block includes a reference to its parent node to verify the continuity of the chain.

Your task is to verify the blockchain and return the balance of the account.

A block is bad if its parent id does not match the id of the preceding block. Your program must also check whether the account has a transaction that would make its balance negative.

The first block (the genesis block) must have parent id 0.

Input

The first line contains one integer $1 \leq N \leq 10^{6}$ , the number of blocks in the chain.

The next $N$ lines each contain three integers: the block id $1 \leq i \leq 10^{6}$ , the parent id $1 \leq p \leq 10^{6}$ , and the amount $-10^{6} \leq m \leq 10^{6}$ transferred to or from the account.

You may assume that no transaction causes an integer underflow or overflow. You may also assume that block ids are unique.

Output

If a transaction makes the account balance lower than 0, print NO_MONEY. If a block is bad, print INVALID. Otherwise, print the final balance of the account as an integer.

Examples2

Example 1
Input
```
2
1 0 5
2 1 -4
```
Expected output
```
1
```

Example 2

Input

Expected output

INVALID