Heroes... ugh...

My plan to destroy the world was almost finished, but now heroes have gathered in their last attempt to save the earth (which, as everybody knows, is pretty flat). Heroes formed a defensive N * M grid, each of the N * M heroes stands in one position of the grid. Also, the hero in position i,j has h_ij life points.

Of course, they stand no chace against my wrath. I'll attack them with Q spells, the i-th spell will have power p_i and will attack the submatrix with corners (r1_i, c1_i) and (r2_i, c2_i). Heroes can decide how to distribute the power of the spell over the heroes in the attacked submatrix, so, for each spell, each hero of the submatrix will decrease his life points by a number of integer points (possibly zero), such that between all the heroes of the submatrix take all the p_i points of damage. Of course, a hero can only take more damage if his life is greater than zero. Note that the damage they receive will accumulate over all the Q spells.

If heroes cannot receive the damage points of a spell, my spell will reach the (flat) earth and immediately destroy it.

Assuming heroes know the sequence of spells I'll use, can they save the earth if they work optimally?

Input

In the first line, two integers, N and M , the number of rows and columns in the grid.

Next N lines, each one contains M integers h_ij , the initial life points of each hero.

Then a line with integer Q, the number of spells.

Then follow Q lines, each with 5 integers: r1_i , c1_i , r2_i , c2_i , p_i .

Output

Print ”BOOM!” (without quotes) if the earth is destroyed, print ”ugh” (without quotes) otherwise.

Example

Input:
2 3
2 1 3
2 4 4
2
1 1 2 2 7
1 2 2 3 9
Output:
ugh

Input:
2 3
2 1 3
2 4 4
2
1 1 2 2 7
1 2 2 3 10

Output:
BOOM!

Constraints

• 1 ≤ N ≤ 10

• 1 ≤ M ≤ 10000

• 1 ≤ Q ≤ 500

• 1 ≤ r1_i ≤ r2_i ≤ N

• 1 ≤ c1_i ≤ c2_i ≤ M

• 1 ≤ p_i , h_ij ≤ 10⁴