H. Portals
time limit per test
2.5 s
memory limit per test
256 MB
input
standard input
output
standard output

Cody and Tyger are together in a place with $$$n$$$ stations and $$$m$$$ portals. Each portal is represented by six numbers $$$(a_1, l_1, r_1, a_2, l_2, r_2)$$$, allowing you to travel from station $$$b$$$ to station $$$c$$$ if and only if all the following conditions are satisfied:

  • $$$l_1 \leq b \leq r_1$$$
  • $$$b \equiv 0 \pmod {a_1}$$$
  • $$$l_2 \leq c \leq r_2$$$
  • $$$c \equiv 0 \pmod {a_2}$$$
You are given a destination $$$d$$$ that Cody and Tyger share. You are also given $$$q$$$ queries, each represented by two integers $$$x$$$ and $$$y$$$. Cody wants to travel from station $$$x$$$ to station $$$d$$$, and Tyger wants to travel from station $$$y$$$ to station $$$d$$$.

Since Cody and Tyger are enemies, they are unwilling to share the same portal during their transportation (they are allowed to be in the same station though). Therefore, for each query, output whether it is possible for both Cody and Tyger to reach station $$$d$$$ without sharing any portals.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 2 \times 10^4)$$$, the number of stations and portals.

The next $$$m$$$ lines contain $$$6$$$ integers each: $$$a_1$$$, $$$l_1$$$, $$$r_1$$$, $$$a_2$$$, $$$l_2$$$, and $$$r_2$$$ $$$(1 \leq a_1, a_2 \leq n, 1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq n)$$$.

The following line contains two integers $$$d$$$ and $$$q$$$ $$$(1 \leq d \leq n, 1 \leq q \leq 2 \times 10^4)$$$, the destination and the number of queries.

The next $$$q$$$ lines contain two integers each: $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq n)$$$.

Output

For each query, output "Yes" if Cody and Tyger can reach station $$$d$$$ without sharing portals, and output "No" otherwise.

Example
Input
6 4
2 2 4 3 3 6
1 4 5 1 6 6
1 1 1 4 3 4
1 1 4 5 1 4
6 4
1 2
1 5
4 4
3 6
Output
Yes
Yes
Yes
No
Note

For the first testcase, Cody can use portal $$$3$$$ to get to station $$$4$$$ and use portal $$$2$$$ to get to station $$$6$$$. Tyger can use portal $$$1$$$ to directly travel to station $$$6$$$.

Credit: C0DET1GER