平面上有 $2N + 1$ 个点。第 $i$ 个点的坐标为 $(X_i, Y_i)$。如果 $X_i = X_j$ 或 $Y_i = Y_j$，则点 $i$ 和点 $j$ 可以配对。

对于每一个点，请确定以下内容： * 如果从点集中移除该点，剩下的 $2N$ 个点能否被分成 $N$ 个不相交的配对？

输入格式

$N$ $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_{2N+1} \ Y_{2N+1}$

数据范围

• $1 \le N \le 100,000$
• $1 \le X_i, Y_i \le 2N + 1$
• 所有点互不相同。
• 输入中的所有值均为整数。

输出格式

输出 $2N + 1$ 行。对于第 $i$ 行，如果移除第 $i$ 个点后，剩下的所有点都能被分成 $N$ 个不相交的配对，则输出 “OK”，否则输出 “NG”。

样例

样例输入 1

1
1 1
1 2
2 1

样例输出 1

NG
OK
OK

样例输入 2

2
1 1
1 2
2 2
2 3
3 3

样例输出 2

OK
NG
OK
NG
OK

样例输入 3

2
1 1
1 2
3 3
4 4
4 5

样例输出 3

NG
NG
OK
NG
NG