Problem Description

On a two-dimensional coordinate plane, you are given $2N+1$ points with distinct coordinates.

Takahashi wants to form many friendly pairs from these points.

Points can form a friendly pair if they satisfy one of the following conditions:

• The two points have the same $x$ coordinate or the same $y$ coordinate.

However, no point can be part of more than one friendly pair.

Takahashi wanted to make all points part of a friendly pair, but he realized it's impossible because the number of points is odd.

Therefore, he thought that if he removes just one point, he could then form $N$ friendly pairs from the remaining $2N$ points.

Determine for each point whether removing it allows forming $N$ friendly pairs from the remaining $2N$ points.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N(1 ≦ N ≦ 100,000)$, representing the number of points.
• The following $2N+1$ lines contain the position information of the points. The $i$-th line contains integers $X_i(1 ≦ X_i ≦ 2N+1)$ and $Y_i(1 ≦ Y_i ≦ 2N+1)$ separated by a space, indicating that the coordinates of the $i$-th point are $(X_i, Y_i)$.
• For $i ≠ j$, it holds that $X_i ≠ X_j$ or $Y_i ≠ Y_j$.

Output Format

Output to the standard output, with a newline at the end.

The output consists of $2N+1$ lines.

The $i$-th line should contain OK if removing the $i$-th point allows forming $N$ friendly pairs from the remaining $2N$ points, or NG if it does not.

Sample Input and Output

Sample Input #1

1
1 1
1 2
2 1

Sample Output #1

NG
OK
OK

Sample Input #2

2
1 1
1 2
2 2
2 3
3 3

Sample Output #2

OK
NG
OK
NG
OK

Sample Input #3

2
1 1
1 2
3 3
4 4
4 5

Sample Output #3

NG
NG
OK
NG
NG

Notes/Hints

Partial Points

If you solve the dataset that additionally satisfies the following constraints, you will be awarded 30 points:

• For all $i(1 ≦ i ≦ 2N)$, it holds that $X_i = X_{i+1}$ or $Y_i = Y_{i+1}$.

Sample Explanation 2

This input/output example satisfies the partial points constraints.

见题面 Input 部分

见题面 Output 部分