VZLA2019H - Heroes

no tags 

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 hij 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 pi and will attack the submatrix with corners (r1i, c1i) and (r2i, c2i). 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 pi 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 hij , 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: r1i , c1i , r2i , c2i , pi .

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 ≤ r1i ≤ r2i ≤ N

• 1 ≤ c1i ≤ c2i ≤ M

• 1 ≤ pi , hij ≤ 104



Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Augusto Hidalgo - Used for Venezuelan 2019 ICPC Local Contest