Problem Description
Rar wants to go out for a walk. The town he lives in can be described as a graph, with N intersections and R roads connecting them. Each road i connects intersection Ai and Bi, and has a length of Li kilometers.
Rar lives at intersection 0. He is planning his walk, and wants to ask Q queries in the form: is there a path I can take such that I will arrive at intersection X after walking K kilometers?
Rar is allowed to travel on a road, or arrive at an intersection more than once, but he cannot switch directions in the middle of a road. In other words, once Rar has started on a road, he cannot stop until he reaches the other intersection.
Input
The first line of input will contain three integers, N, R and Q.
The next R lines will describe a graph, with each line i containing Ai, Bi and Li.
The next Q lines will contain two integers each, X and K for that query.
Output
The output should contain Q lines, with each line stating "YES" or "NO", depending whether such a path is possible.
Limits
0 ≤ X, Ai ≠ Bi < N.
Subtask 1 (13%): 1 ≤ N, R ≤ 1000, Li = 1, 0 ≤ K ≤ 104, 1 ≤ Q ≤ 106.
Subtask 2 (23%): 1 ≤ N, R ≤ 1000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 104, 1 ≤ Q ≤ 106.
Subtask 3 (12%): 1 ≤ N, R ≤ 1000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.
Subtask 4 (16%): 1 ≤ N, R ≤ 30000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, Q = 1.
Subtask 5 (15%): 1 ≤ N, R ≤ 30000, Li = 1, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.
Subtask 6 (21%): 1 ≤ N, R ≤ 30000, 1 ≤ Li ≤ 100, 0 ≤ K ≤ 109, 1 ≤ Q ≤ 106.
Subtask 7 (0%): Sample Testcases.
Sample Testcase 1
Input
3 3 4
0 1 3
0 2 1
1 2 1
1 3
1 2
1 5
2 2
Output
YES
YES
YES
NO
Sample Testcase 2
Input
4 3 3
0 1 2
0 2 4
2 3 1
2 8
2 7
3 5
Output
YES
NO
YES