问题文

在二维坐标平面上，给定 $2N+1$ 个不同坐标的点。

高桥君要从这些点中创建尽可能多的好朋友组合。

满足以下条件的点之间可以成为好朋友组合：

• 两个点的 $x$ 坐标或者 $y$ 坐标中的一个相等。

但每个点不能与两个以上的点成为好朋友组合。

高桥君希望把所有的点都组合成好朋友，但是由于点的数量是奇数，所以发现这是不可能的。

因此，他想删除其中一个点，然后创建 $N$ 对好朋友组合，这样就能使所有的点都成为好朋友组合。

请判断对于所有的点，删除某个点后，剩下的 $2N$ 个点是否可以创建出 $N$ 对好朋友组合。

---

输入

输入数据从标准输入中获取，格式如下：

$N$

$X_1$ $Y_1$

$X_2$ $Y_2$

:

$X_{2N+1}$ $Y_{2N+1}$

• 第一行是一个整数 $N(1 ≦ N ≦ 100,000)$，表示点的数量。
• 接下来 $2N+1$ 行，给出了点的位置信息。其中第 $i$ 行包含两个用空格分隔的整数 $X_i(1 ≦ X_i ≦ 2N+1)$ 和 $Y_i(1 ≦ Y_i ≦ 2N+1)$，表示第 $i$ 个点的坐标为 $(X_i, Y_i)$。
• 对于任意的 $i$ 和 $j$，满足 $i ≠ j$ 的条件下，有 $X_i ≠ X_j$ 或者 $Y_i ≠ Y_j$。

输出

输出结果到标准输出，末尾包含换行符。

输出共有 $2N+1$ 行。

对于第 $i$ 行的点被删除后，判断剩下的 $2N$ 个点能否创建出 $N$ 对好朋友组合，如果可以则输出 OK，否则输出 NG。

---

部分点

对于以下附加约束的数据集，如果能正确输出则可以获得 30 分。

• 对于所有的 $i(1 ≦ i ≦ 2N)$，满足条件 $X_i = X_{i+1}$ 或者 $Y_i = Y_{i+1}$。

---

示例输入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

---