This is a classic problem.

Given $n$ rectangles, the $i$-th rectangle has dimensions $w_i \times h_i$. There is a game where, in each turn, a player can choose a rectangle and a cutting direction to divide it into $k > 1$ equal pieces, provided that the dimensions of the resulting pieces remain integers. For the $i$-th rectangle, there are parameters $a_i, b_i \in \{0, 1\}$. If $a_i = 1$, both players can cut the $i$-th rectangle (and all smaller rectangles derived from it) horizontally along the $w$ dimension; otherwise, only the first player can cut horizontally. If $b_i = 1$, both players can cut the $i$-th rectangle (and all smaller rectangles derived from it) vertically along the $h$ dimension; otherwise, only the second player can cut vertically.

Given $q$ queries, each query $i$ asks whether the first player can win if only the rectangles from $l$ to $r$ are available.

Input

The first line contains two integers $n$ and $q$.

The next $n$ lines each contain four integers $a_i, b_i, w_i, h_i$, describing each rectangle.

The next $q$ lines each contain two integers $l_i, r_i$.

Output

Output a single line. For each query, output Y if the first player can win, otherwise output N.

Examples

Input 1

6 8
1 0 3 5
0 1 5 10
1 1 6 4
1 1 8 12
0 1 4 6
1 0 8 10
1 2
1 4
1 5
2 4
2 5
3 3
3 6
4 4

Output 1

NNNNNYYY

Examples 2

See the provided files.

Subtasks

For all data, $1 \le n \le 10^5$, $1 \le q \le 10^6$, $1 \le h_i, w_i \le 10^5$, $1 \le l_i \le r_i \le n$.

• Subtask 1 (10 points): $n, q \le 10$.
• Subtask 2 (20 points): $n \le 2\,000$.
• Subtask 3 (15 points): $a_i = b_i = 1$.
• Subtask 4 (5 points): $a_i = 1$.
• Subtask 5 (5 points): $b_i = 1$.
• Subtask 6 (45 points): No additional restrictions.