$n$-皇后问题是一个棋盘谜题，玩家需要尝试在 $n \times n$ 的棋盘上放置 $n$ 个皇后，使得没有任何两个皇后互相“攻击”。对于所有的 $n$ 值，该问题都有解。

在国际象棋中，皇后可以垂直、水平或对角线移动任意数量的格子。在下图中，皇后可以移动到任何带有绿色圆点的格子。

来源：learnchessrules.com

如果一个皇后可以立即移动到另一个棋子当前占据的格子，那么它就在“攻击”那个棋子。你的任务是，给定一个放置了 $k$ 个皇后的 $n \times n$ 棋盘，检查是否有任何指定的皇后互相攻击。

输入格式

输入的第一行包含一对数字 $n$ 和 $k$，其中 $n$ 是棋盘的大小，$k$ 是皇后的数量。这里 $1 \le n \le 1000$ 且 $1 \le k \le n$。接下来的 $k$ 行包含一对数字 $(i, j)$，其中 $1 \le i \le n$ 且 $1 \le j \le n$。每个 $(i, j)$ 表示一个放置在第 $i$ 列（从左侧起）和第 $j$ 行（从底部起）的皇后。没有两个指定的皇后会占据同一个格子。请参考下方的样例。

输出格式

如果没有任何皇后互相攻击，输出一行单词 “Valid”，否则输出 “Invalid”。

样例

样例输入 1

4 4
1 2
2 4
3 1
4 3

样例输出 1

Valid

样例输入 2

4 2
1 1
4 4

样例输出 2

Invalid