Problem Description

Recently, a fashionable game called Platoon Match (squad battle) has become popular among the youth in a certain city. It is a team battle where participants, armed with water guns and dressed in raincoats, race around the field to compete for the number of times they can hit opponents with water.

Here are the detailed rules. First, $ N $ participants (not necessarily evenly divided) are split into two teams. Everyone simultaneously departs from their respective team's base and moves within the prepared field aiming to hit members of the opposing team with their water guns. During the game, if a person is hit by a water gun from an opponent, they temporarily leave the game and immediately return to their team's base to rejoin. At the end of the game, each participant self-reports the number of times they were hit and the number of times they hit the enemy, which determines the outcome of the game.

You have been keeping records of past Platoon Matches, but you forgot to record the team divisions for each game, and now you only know how many times each participant hit and was hit. Are these records consistent? For now, you decided to check if there exists a team division that can realize the recorded performance of each participant.

Input Format

The record of one Platoon Match game is given from standard input in the following format:

$ N $ $ k1 $ $ d1 $ : $ kN $ $ dN $

$ N $ ($2 \leq N \leq 200$) represents the number of participants in the game. $ ki $ and $ di $ ($1 \leq i \leq N$, $0 \leq ki, di \leq 200$) respectively denote the number of times the $ i $th participant hit the enemy and was hit by the enemy.

Output Format

If there exists a team division that is consistent with the given performance of each person, output valid; otherwise, output invalid. End the output with a newline.

Sample Input and Output

Sample Input #1

3
7 2
1 3
1 4

Sample Output #1

valid

Sample Input #2

3
2 5
3 2
4 2

Sample Output #2

invalid

Sample Input #3

3
4 1
2 1
1 1

Sample Output #3

invalid

Sample Input #4

4
0 0
0 0
0 0
0 0

Sample Output #4

valid

Notes/Hints

Sample Explanation 1

If the 1st participant is in team 1 and the 2nd and 3rd participants are in team 2, there is no contradiction. (It can be considered that participant 1 hit participant 2 three times and participant 3 four times, and participants 2 and 3 each hit participant 1 once.)

Sample Explanation 2

No matter how the teams are divided, a contradiction arises.

Sample Explanation 3

The total number of hits and the total number of times hit do not match.

Sample Explanation 4

No matter how the teams are divided, there is no contradiction.

见题面 Input 部分

见题面 Output 部分