J. Tyger's Minecraft Park
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Codetiger is playing Minecraft with his friends again. His current world is a 2d park that can be represented on an infinite cartesian plane. In the park there are $$$n$$$ axis-aligned square trees, each centered at location $$$(x_i, y_i)$$$ and having side length $$$s_i$$$. No two trees have intersecting area in this world.

After his Minecraft dog was killed by one of his friends he decides to be more careful. To do so, he wants to make sure his new dog has various escape paths. As his dog and house will be at different locations over time and his dog is still growing, he needs to test if an escape path exists between various different points for various sizes of his dog. The dog can walk along any continuous path in the 2d world as long as at no point the area of the dog intersects the area of any trees. The dog is also an axis-aligned square. Note that the dog's movement is also axis-aligned.

As Codetiger is training to be a CEO and therefore practices delegating work to others (like the problem writing of this contest), he decides to ask you $$$q$$$ queries about his dog's possible escape paths. Each specifies the center location of the dog where it starts $$$(sx_i, sy_i)$$$, the center location of the dog where it should end up in Codetiger's potential new house $$$(ex_i, ey_i)$$$, and the side length of the dog $$$d_i$$$. It is guaranteed the dog will not intersect any trees at the start and end locations in any queries.

For each query you must answer whether any continuous escape path exists between the locations so that the dog intersects no trees. Output WOOF if one exists or MEOW otherwise.

Input

The first line contains $$$n$$$, and $$$q$$$  — the number of trees and the number of queries. $$$(1 \leq n,q \leq 3 \times 10^4)$$$

Each of the next $$$n$$$ lines contains three integers, $$$x_i$$$, $$$y_i$$$, and $$$s_i$$$  — the $$$x$$$ and $$$y$$$ coordinates and side length of the tree. $$$(1 \leq x_i,y_i,s_i \leq 10^6)$$$

Each of the next $$$q$$$ lines contains three integers, $$$sx_i$$$, $$$sy_i$$$, $$$ex_i$$$, $$$ey_i$$$, and $$$d_i$$$  — the $$$x$$$ and $$$y$$$ coordinates of the query's starting position, ending position, and side length of the dog. $$$(1 \leq sx_i,sy_i,ex_i,ey_i,d_i \leq 10^6)$$$

Output

For each query, respond either WOOF if there is a valid path or MEOW if not.

Example
Input
20 2
12 12 4
25 9 4
9 23 5
16 22 4
23 13 2
24 16 2
20 14 1
0 15 3
0 21 3
20 17 5
21 4 5
20 24 4
0 10 2
19 10 2
11 19 1
6 16 2
5 20 1
9 13 2
17 14 1
24 25 1
14 16 6 7 4
6 12 24 20 1
Output
MEOW
WOOF