Block

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem C: ブロック

A さんの家に親戚の B 君がやってきました。彼は 3 歳でブロックが大好きです。彼が持っているブ ロックは図 1 のような形をしています。

図1

B 君はボードの上にブロックを敷き詰めています。彼に「何を作っているの?」と聞くと、彼は「迷路!!」と元気よく答えました。彼の言う迷路とは、スタートからゴールまで側面が接している、同じ色のブロックだけでたどることができるブロックの配置のことだそうです。図 2 は黄色のブロックにより、左上(スタート)から右下(ゴール)へ迷路ができていることを表しています。

図2

無邪気に遊んでいる B 君を横目に、冷静なプログラマーであるあなたは、ブロックの並びが迷路となっているかを確かめてみることにしました。

ブロックの情報とスタート、ゴールの座標を入力とし、ブロックが迷路となっていれば OK 、なっていなければ NG を出力するプログラムを作成してください。 ボードは横方向に w 、縦方向に h(それぞれ 4 以上 100 以下の整数)の大きさをもち、 左上の座標は( 1 , 1 )、右下の座標は( w , h )とします。ブロックは 2 × 4 の長方形ですべて同じ大きさです。ブロックの色 c は 1(白)、2(黄)、3(緑)、4(青)、5(赤)のいずれかです。ブロックのボード上での向き d は 横方向に長い場合 0 、 縦方向に長い場合 1 とします。 ブロックの位置はブロックの左上の座標( x , y )によって表されます。なお、ブロックの位置は他のブロックと重なることは無く、ボードからはみ出すこともありません。

Input

複数のデータセットの並びが入力として与えられます。 入力の終わりはゼロふたつの行で示されます。 各データセットは以下のとおりです。

1 行目 ボードの大きさ w h (整数 整数;半角空白区切り)
2 行目 スタートの座標 xs ys (整数 整数;半角空白区切り)
3 行目 ゴールの座標 xg yg (整数 整数;半角空白区切り)
4 行目 ブロックの個数 n (整数)
5 行目 第 1 のブロックの情報 c d x y (整数 整数 整数 整数;半角空白区切り)
各記号の意味は以下のとおりです。
c : ブロックの色
d : ブロックの向き
x , y : ブロックの位置
6 行目 第 2 のブロックの情報
.
.
n+4 行目 第 n のブロックの情報

Output

入力データセットごとに、判別結果を出力します。

Sample Input

20 20 
1 1
9 9
7
2 0 1 1
5 1 1 3
2 1 3 3
1 1 5 2
5 1 7 3
2 0 2 7
2 0 6 8
20 20
9 9
1 1
6
2 0 1 1
1 0 5 1
2 1 1 3
5 0 1 7
3 1 5 5
4 1 8 5
0 0

Output for the Sample Input

OK
NG

Source: PC Koshien 2009 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2009-11-14
http://www.pref.fukushima.jp/pc-concours/