問題文

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

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

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

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

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