问题描述

最近在某个城市的年轻人中流行一种潮流游戏叫做"Platoon Match"（小队战斗）。参与者手持水枪，身穿雨衣，在指定场地内奔跑，竞争用水枪击中对方的次数。

以下是详细规则。首先，参与者被分为两个队伍（人数不一定相等）。所有人从各自队伍的基地同时出发，在规定的场地内移动并尝试用水枪击中敌对队伍的成员。在游戏中被敌对队伍的成员用水枪击中的人会暂时退出游戏，并立即返回自己队伍的基地重新参加游戏。游戏结束后，每个参与者申报自己被击中的次数和击中敌对成员的次数，以决定游戏的胜负。

现在，你记录了之前几场"Platoon Match"的成绩，但忘记记录每场游戏的队伍分配情况，只知道每位参与者击中和被击中的次数。首先你要确定是否存在一种队伍分配方式，能够实现记录中每个参与者的成绩。

输入

给定一场"Platoon Match"的记录，以以下格式从标准输入读取：

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

$N$（$2 \leq N \leq 200$）表示参与游戏的人数。$ki$和$di$（$1 \leq i \leq N$，$0 \leq ki, di \leq 200$）分别表示第$i$位参与者击中敌对成员的次数和被击中的次数。

输出

如果存在一种队伍分配方式，能够实现记录中每个参与者的成绩，输出"valid"；否则输出"invalid"，并换行。

示例1

3
7 2
1 3
1 4

输出1

valid

将参与者1分到队伍1，参与者2和3分到队伍2时，不会产生矛盾。（可以认为参与者1击中参与者2 3次，击中参与者3 4次，参与者2和3各击中参与者1 1次。）

示例2

3
2 5
3 2
4 2

输出2

invalid

无论如何进行队伍分配，都会产生矛盾。

示例3

3
4 1
2 1
1 1

输出3

invalid

所有参与者的击中次数总和与被击中次数总和不相等。

示例4

4
0 0
0 0
0 0
0 0

输出4

valid

无论如何进行队伍分配，都不会产生矛盾。