nemo

Due to an accident, Martin the clownfish has lost his only son, Nemo. Now, Martin wants to know if it is possible for him to even find Nemo.

In the oceans, there are a total of N different places connected by E different convection currents which brings you from one place to another almost instantly. For the sake of simplicity, we assume that the convection currents are bi-directional.

However, convection currents do not function all the time. Some ocean currents might only be available in the night while others during the day only. For this problem, we shall assume that each convection current has a specified 'opening time' and a 'closing time'. The convection current will be functional between the 'opening time' and 'closing time' inclusive.

For convenience, places are labelled from 0 to N-1 and Martin is currently at location X while Nemo is currently at location Y. Martin wants to know whether it is possible to get to Nemo assuming the current time is T.

To do so, Rar the Cat was enlisted to help Martin out. Rar the Cat has noticed that all the convection currents will open before any of the convection currents close. In other words, no 'opening time' will be later than any of the 'closing times' of other currents.

Input

The first line of input will contain 2 integers, N and E.

Subsequent E lines will contain 4 integer on each line: A, B, O, C. This means that there exist a convection current from place A to place B with 'opening time' O and 'closing time' C.

This problem has multiple testcases, the next line will contain an integer TC, denoting the number of testcases that will follow.

There will be a single testcase per subsequent TC lines. Each testcase contains 3 integers, X, Y and T. You are to answer if Martin can travel from X to Y instantly at time T.

Output

For each testcase, output 'Y' on a single line if Martin can travel from X to Y instantly at time T. If not, output 'N' on a single line instead.

Limits

0 ≤ A, B, X, Y < N

0 ≤ T, O, C ≤ 2000000000

It is guaranteed that A ≠ B and X ≠ Y

Unless otherwise stated, there will not be more than 100000 testcases. (TC ≤ 100000)

Subtasks

Subtask 1 (7 marks): N = 2, E = 1, TC = 10

Subtask 2 (25 marks): 0 < N ≤ 50000, 0 < E ≤ 100000, all O = 0, all C = 2000000000

Subtask 3 (29 marks): 0 < N ≤ 50000, 0 < E ≤ 100000, TC= 10

Subtask 4 (39 marks): 0 < N ≤ 50000, 0 < E ≤ 100000

Subtask 5 (0 marks): Sample Testcases

Sample Input 1

2 1
0 1 13 17
10
0 1 10
1 0 11
0 1 12
0 1 13
0 1 14
1 0 15
0 1 16
0 1 17
1 0 18
0 1 19

Sample Output 1

N
N
N
Y
Y
Y
Y
Y
N
N

Sample Input 2

6 8
0 1 5 11
0 2 0 15
1 3 9 20
1 4 7 15
2 3 2 12
2 4 9 15
3 5 7 20
4 5 10 10
10
0 5 10
0 5 13
4 5 10
2 5 13
4 5 20
1 5 20
0 5 21
0 2 3
0 3 3
0 4 3

Sample Output 2

Y
Y
Y
Y
N
Y
N
Y
Y
N

Sample Input 3

4 2
0 1 1 20
2 3 1 20
10
0 1 20
0 1 1
0 1 21
0 1 0
0 3 10
1 2 10
0 2 10
2 3 21
2 3 20
3 2 0

Sample Output 3

Y
Y
N
N
N
N
N
N
Y
N