这是一道大原题。

给定 $n$ 个矩形，第 $i$ 个大小为 $w_i \times h_i$。现在有一个博弈，每次玩家可以选择一个矩形，以及一个可以切的方向，均匀切成 $n > 1$ 份，要求切完后长宽仍是整数。对于第 $i$ 个矩形，还会有参数 $a_i, b_i \in \{0, 1\}$。若 $a_i = 1$，则第 $i$ 个矩形与它切出来的所有小矩形双方都可以在 $w$ 这一维横着切，否则只有左方能横着切。若 $b_i = 1$，则第 $i$ 个矩形与它切出来的所有小矩形双方都可以在 $h$ 这一维竖着切，否则只有右方能竖着切。

现在给定 $q$ 个询问，第 $i$ 个询问为若仅留下第 $l \sim r$ 个矩形，左方先手能否获胜。

输入格式

输入的第一行包含两个整数 $n, q$。

接下来 $n$ 行，每行四个整数 $a_i, b_i, w_i, h_i$，描述每个矩形。

接下来 $q$ 行，每行两个整数 $l_i, r_i$。

输出格式

输出一行，对于每个询问，如果可以获胜，输出 Y，否则输出 N。

样例数据

样例 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

样例 1 输出

NNNNNYYY

样例 2

见下发文件。

子任务

对于所有数据，$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 分）：$n,q \le 10$。
• Subtask 2（20 分）：$n \le 2\,000$。
• Subtask 3（15 分）：$a_i = b_i = 1$。
• Subtask 4（5 分）：$a_i = 1$。
• Subtask 5（5 分）：$b_i = 1$。
• Subtask 6（45 分）：没有额外的限制。