아미다쿠지

아미다쿠지는 동아시아에서 널리 쓰이는 추첨 방법이다. 여러 개의 선물을 사람들에게 나눠 주거나 여러 개의 작업을 배정할 때 자주 쓴다.

그림 B-1은 아미다쿠지의 예이다. 세로선을 여러 개 긋는데, 세로선의 개수는 참가자 수와 같다. 인접한 두 세로선 사이에 가로 막대를 여러 개 긋는다. 막대의 개수와 위치는 자유지만, 두 막대가 끝점을 공유할 수는 없다. 보통은 가로 막대를 무작위로 많이 긋는다.

아미다쿠지를 쓰려면 먼저 세로선의 아래쪽 끝에 상품이나 작업의 이름을 적는다. 그다음 참가자마다 서로 다른 세로선의 위쪽 끝을 하나씩 고른다. 참가자는 고른 선을 따라 위에서 아래로 내려간다. 가로 막대를 만나면 그 막대를 따라 연결된 옆 세로선으로 옮겨 가 계속 아래로 내려간다. 세로선의 아래쪽 끝에 도달하면 거기 적힌 항목이 받을 선물이나 배정받을 작업이 된다.

그림 B-2는 위쪽 끝 P를 골랐을 때의 경로이다. 이 경우 R의 항목을 얻는다.

그림 B-2에서 P를 고른 참가자가 Q의 항목을 원한다고 하자. 그러나 Q에는 도달하지 못한다. 방금 도입된 특별한 규칙이 그 소원을 이뤄 줄 수 있다. 새 규칙으로는 임의의 위치에 가로 막대를 하나 추가할 수 있다. 그림 B-3에서 X로 표시한 막대를 추가하면 경로가 Q에 도달한다.

이 문제의 목표는 주어진 아미다쿠지에 가로 막대를 하나 추가해서, 지정한 세로선의 위쪽 끝에서 출발한 경로가 지정한 세로선의 아래쪽 끝에 도달하게 하는 프로그램을 작성하는 것이다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

$n$ $m$ $p$ $q$ $x_1$ $\cdots$ $x_m$

입력의 모든 값은 양의 정수이다. $n$은 세로선의 개수이고, $m$은 원래 아미다쿠지에 있는 가로 막대의 개수이다. 왼쪽에서 $p$번째 세로선의 위쪽 끝을 고른 참가자는 왼쪽에서 $q$번째 세로선의 아래쪽 끝에 도달하기를 원한다. $2 \le n \le 50$, $m \le 500$, $p \le n$, $q \le n$이다.

$x_1, \ldots, x_m$은 가로 막대의 위치이다. $x_k$는 위에서 $k$번째 막대의 위치이다. 모든 막대의 세로 위치는 서로 다르다. $x_k \le n-1$이며, 막대는 왼쪽에서 $x_k$번째 세로선과 $(x_k+1)$번째 세로선을 잇는다.

입력의 끝은 0이 네 개 있는 줄이다. 데이터셋은 300개를 넘지 않는다.

각 데이터셋에 대해 다음 중 하나를 한 줄에 출력한다.

• 가로 막대를 추가하지 않고도 $p$에서 $q$에 도달할 수 있으면 OK를 출력한다.
• 그렇지 않고, 가로 막대를 하나 추가해도 $p$에서 $q$에 도달할 수 없으면 NG를 출력한다.
• 그 밖의 경우에는 공백으로 구분된 두 정수 $x$와 $y$를 출력한다. 이는 $x$번째 세로선과 $(x+1)$번째 세로선을 잇는 막대를 위에서 $y$번째 막대와 $(y+1)$번째 막대 사이 높이에 추가한다는 뜻이다. 가장 위의 막대보다 위에 추가하면 $y$는 0이다. 가장 아래 막대보다 아래에 추가하면 $y$는 $m$이다. 적절한 위치가 둘 이상이면 $y$가 가장 작은 위치를 고른다.

OK와 NG는 대문자로 쓴다.