問題文

最近ある街の若者の間では Platoon Match （小隊バトル） というハイカラな遊びが流行っている。 水鉄砲を携えレインコートに身を包み、フィールド内を駆け回って敵に水を当てた回数を競うチーム戦である。

以下に詳細なルールを記す。まず $N$ 人の参加者が（人数が均等とは限らない） $2$ つのチームに分かれる。全員それぞれのチームの本陣から一斉に出発し、用意されたフィールド内を移動して敵チームのメンバーに水鉄砲を当てることを目指す。ゲーム中に敵チームのメンバーに水鉄砲で撃たれた人は一時的にゲームから抜け、即座に自分のチームの本陣に戻って再びゲームに参加する。ゲーム終了時にそれぞれの参加者は自分が敵に撃たれた回数と敵を撃った回数を自己申告し、ゲームの勝敗を決定する。

さて、あなたはこれまでの Platoon Match の記録を取っていたのだが、それぞれのゲームのチーム分けを記録し忘れており、各参加者が何回撃ったか・撃たれたかしか分からないようになっていた。そもそもこの記録はつじつまが合っているのだろうか？ひとまずあなたは記録されている各参加者の成績を実現するようなチーム分けが存在するかどうか確かめることにした。

入力

Platoon Match $1$ ゲームの記録が以下の形式で標準入力から与えられる。

$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$ 行に出力せよ。出力の末尾に改行を入れること。

入力例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

どのようにチーム分けしても矛盾しない。