#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 *A _{i}* and

*B*, and has a length of

_{i}*L*kilometers.

_{i}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 *A _{i}*,

*B*and

_{i}*L*.

_{i}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, A_{i} ≠ B_{i} < N.

Subtask 1 (13%): 1 ≤ N, R ≤ 1000, L_{i} = 1, 0 ≤ K ≤ 10^{4}, 1 ≤ Q ≤ 10^{6}.

Subtask 2 (23%): 1 ≤ N, R ≤ 1000, 1 ≤ L_{i} ≤ 100, 0 ≤ K ≤ 10^{4}, 1 ≤ Q ≤ 10^{6}.

Subtask 3 (12%): 1 ≤ N, R ≤ 1000, 1 ≤ L_{i} ≤ 100, 0 ≤ K ≤ 10^{9}, 1 ≤ Q ≤ 10^{6}.

Subtask 4 (16%): 1 ≤ N, R ≤ 30000, 1 ≤ L_{i} ≤ 100, 0 ≤ K ≤ 10^{9}, Q = 1.

Subtask 5 (15%): 1 ≤ N, R ≤ 30000, L_{i} = 1, 0 ≤ K ≤ 10^{9}, 1 ≤ Q ≤ 10^{6}.

Subtask 6 (21%): 1 ≤ N, R ≤ 30000, 1 ≤ L_{i} ≤ 100, 0 ≤ K ≤ 10^{9}, 1 ≤ Q ≤ 10^{6}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 13 | 20 | 2s | 256MB | Minimum |

2 | 23 | 42 | 2s | 256MB | Minimum |

3 | 12 | 62 | 2s | 256MB | Minimum |

4 | 16 | 20 | 2s | 256MB | Minimum |

5 | 15 | 40 | 2s | 256MB | Minimum |

6 | 21 | 122 | 2s | 256MB | Minimum |

7 | 0 | 2 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o walk -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512