Block

Relative B came to Mr. A's house. He is 3 years old and loves blocks. The block he has is shaped like Figure 1.

Figure 1

Mr. B is laying blocks on the board. When I asked him, "What are you making?", He replied cheerfully, "Maze !!". The maze he says is the arrangement of blocks that are in contact with each other from the start to the goal and can be traced only by blocks of the same color. Figure 2 shows that the yellow block creates a maze from the upper left (start) to the lower right (goal).

Figure 2

With Mr. B playing innocently, you, the programmer, decided to see if the blocks were arranged in a maze.

Create a program that inputs the block information, start, and goal coordinates, and outputs OK if the block is a maze, and NG if it is not. The board has the size of w in the horizontal direction and h in the vertical direction, and the upper left coordinate is (1, 1) and the lower right coordinate is (w, h). The blocks are 2x4 rectangles, all the same size. The block color c can be 1 (white), 2 (yellow), 3 (green), 4 (blue), or 5 (red). The orientation d of the block on the board is 0 if it is long horizontally and 1 if it is long vertically. The position of the block is represented by the coordinates (x, y) at the top left of the block. The position of the block does not overlap with other blocks and does not protrude from the board.

Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

w h xs ys ys xg yg n c1 d1 x1 y1 c2 d2 x2 y2 :: cn dn xn yn

The board size w, h (4 ≤ w, h ≤ 100) is given on the first line. The second line gives the start coordinates xs, ys, and the third line gives the goal coordinates xg, yg.

The number of blocks n is given on the 4th line. The next n lines are given the color ci, orientation di, position xi, yi of the i-th block.

The number of datasets does not exceed 30.

Output

The discrimination result is output to one line for each input data set.

Example

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

OK NG

inputFormat

inputs the block information, start, and goal coordinates, and

outputFormat

outputs OK if the block is a maze, and NG if it is not. The board has the size of w in the horizontal direction and h in the vertical direction, and the upper left coordinate is (1, 1) and the lower right coordinate is (w, h). The blocks are 2x4 rectangles, all the same size. The block color c can be 1 (white), 2 (yellow), 3 (green), 4 (blue), or 5 (red). The orientation d of the block on the board is 0 if it is long horizontally and 1 if it is long vertically. The position of the block is represented by the coordinates (x, y) at the top left of the block. The position of the block does not overlap with other blocks and does not protrude from the board.

Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

w h xs ys ys xg yg n c1 d1 x1 y1 c2 d2 x2 y2 :: cn dn xn yn

The board size w, h (4 ≤ w, h ≤ 100) is given on the first line. The second line gives the start coordinates xs, ys, and the third line gives the goal coordinates xg, yg.

The number of blocks n is given on the 4th line. The next n lines are given the color ci, orientation di, position xi, yi of the i-th block.

The number of datasets does not exceed 30.

Output

The discrimination result is output to one line for each input data set.

Example

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

OK NG

样例

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

OK
NG

</p>