007 - あみだくじ

あみだくじ

あみだくじは，東アジアでよく使われる抽選の方式である． 複数の人に，1 つずつ景品を割り当てたり，仕事を割り振ったりするのによく使われる．

図 B-1 があみだくじの例である (Sample Input の最初のデータセットに対応)． 人数と同じ本数の縦線を平行に引く． そして，いくつかの隣り合う縦線の間に何本かの横線を縦線に垂直に引く． 横線の本数や位置は任意だが，2 本の横線の端点が一致してはならない． 普通は多数の横線をランダムに引く．

あみだくじを使うときは，まず，縦線の下端に景品や仕事の名前を書く． 次に各参加者はそれぞれ違う縦線の上端を選ぶ． そして，選んだ縦線を上端から下向きにたどっていく． 横線との T 字路に達したらその横線を通って反対側の縦線に移り，下に向かっての移動を続ける． 縦線の下端に達したら，そこに書いてある景品や仕事が与えられる． 縦線の上端 P を選んだ場合を図 B-2 に示す． この場合，得られるのは R にある景品や仕事である．

仮に P を選んだ参加者が実は Q にあるものが欲しかったとしたら，それは叶っていない． しかし，待ってほしい． 新設されたばかりの特別ルールによればこの望みは叶えられるかもしれない． 新ルールでは好きな場所に横線を 1 本だけ追加してよいのだ． 実際，図 B-3 のように横線 X を追加すれば Q に行けるではないか．

与えられたあみだくじに 1 本だけ横線を加えて，指定された縦線の上端から指定された縦線の下端に到達するようにするには，横線をどこに加えればよいかを答えるプログラムを書きなさい．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n m p q
x₁ ⋯ x_m

データセット中の項目は，すべて正の整数である． n は縦線の本数を表す． m は元のあみだくじの横線の本数を表す． 左から p 番目の縦線の上端を選んだ参加者が，左から q 番目の縦線の下端に到達したいものとする． 2 ≤ n ≤ 50，m ≤ 500，p ≤ n，q ≤ n が成り立つと仮定してよい．

x₁, …, x_m は元のあみだくじの横線の位置を表す． x_k が上から k 番目の横線の位置である． x_k ≤ n − 1 が成り立つ． この横線は，左から x_k 番目の縦線と x_k + 1 番目の縦線を結んでいる． この入力形式から，横線の上下方向の位置 (高さ) はすべて異なっていることが保証される．

入力の終わりは，4 つのゼロだけからなる行で表される． 入力中のデータセットの個数は 300 を超えない．

Output

各データセットに対して，次のいずれかからなる行を出力すること．

• 横線を加えなくても p から q に到達する場合，OK．
• そうではなく，1 本の横線をどこに加えても p から q に到達するようにできない場合，NG．
• それ以外の場合，加える横線の位置を表す 2 つの整数 x と y を空白で区切ったもの． 左から x 番目の縦線と x + 1 番目の縦線を結ぶ横線を，上から y 番目の横線と y + 1 番目の横線の間の高さに追加することを意味する． 一番上の横線より上に追加する場合は y = 0 とすること． 一番下の横線より下に追加する場合は y = m とすること． 目的を達する横線の加え方が複数ある場合は，y が最小のものを答えること．

OK と NG は，大文字で出力すること．

Sample Input

5 8 3 4
2 1 4 2 3 1 3 2
5 8 3 3
2 1 4 2 3 1 3 2
5 8 3 1
3 1 4 2 2 4 1 3
4 8 1 4
3 1 3 1 3 1 3 1
0 0 0 0

Output for the Sample Input

2 6
OK
NG
2 2