Problem Description
Peanut has recently taken up a truck driving job! (what?) He now needs to deliver some stuff to some people in his city. His city can be represented in a graph of N nodes and N-1 edges, with each road i connecting nodes Ai and Bi. Every two nodes are connected by exactly one path. Peanut's factory is located at node 0. Each road will also have a certain length Wi, which is defined by the amount of time it takes to traverse that edge.
Today, Peanut has Q deliveries to make, each delivery i being at time Ti and toward node Mi. Peanut can send his minions to deliver these goods, and they must leave exactly at time Ti and are not allowed to "wait" at nodes, travel back and forth edges, or anything to stall time. They must go straight to the destination node using the shortest path. (they do not need to return.)
Now, here is the problem. To save electricity, his city has decided to close roads at certain times, so each road i will only be open from time Si to Ei inclusive. To clarify, Peanut's minions can enter the road within the time period. His exit time is not limited. Therefore, help Peanut determine if he is able to execute each delivery.
Input
The first line of input will contain two integers, N and Q.
The next N-1 lines of input will contain five integers for each edge, representing Ai, Bi, Wi, Si and Ei.
The next Q lines of input will contain two integers each, Mi and Ti for each delivery.
Output
Your program should output either a "YES" or a "NO" on a single line for each delivery, representing whether the delivery can be done.
Limits
1 ≤ N ≤ 100 000. 1 ≤ Q ≤ 300 000. 0 ≤ Wi, Si, Ei, ≤ 1 000 000.
Subtask 1 (12%): All road lengths are 0, Q ≤ 20.
Subtask 2 (14%): Q ≤ 20.
Subtask 3 (23%): Si = 0.
Subtask 4 (24%): 1 ≤ N ≤ 1 000. 1 ≤ Q ≤ 3 000.
Subtask 5 (27%): No other constaints apply.
Subtask 6 (0%): Sample testcases.
Sample Input 1
3 5
0 1 0 3 5
1 2 0 1 3
2 3
2 5
2 1
1 4
1 2
Sample Output 1
YES
NO
NO
YES
NO
Sample Input 2
6 3
0 5 2 2 6
4 5 2 2 6
2 5 1 4 5
0 3 3 1 5
1 3 2 2 4
4 1
4 2
3 5
Sample Output 2
NO
YES
YES