問題文

二次元座標平面上に、座標の異なる $2N+1$ 個の点が与えられます。

高橋君はこの点の中からたくさんの仲良しペアを作ります。

以下の条件を満たす点同士は仲良しペアになれます。

• $2$ つの点の $x$ 座標と $y$ 座標のどちらかが等しい。

ただしどの点も $2$ つ以上の点と仲良しペアになることはできません。

高橋君は、全ての点を仲良しペアにしたかったのですが、点の数が奇数なので不可能なことに気がつきました。

なのでどれか $1$ 個だけ点を削除し、そのあと $N$ 組の仲良しペアを作れば全ての点を仲良しペアにできると考えました。

すべての点について、その点を削除すると残りの $2N$ 個の点から $N$ 組の仲良しペアが作れるかどうかを判定してください。

---

入力

入力は以下の形式で標準入力から与えられる。

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

• $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$ ならば、$X_i ≠ X_j$ または $Y_i ≠ Y_j$ を満たす。

出力

出力は標準出力に行い、末尾に改行を入れること。

出力は $2N+1$ 行からなる。

$i$ 行目には、$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

---