The squirrel nation is preparing to establish an advanced highway system to connect their cities. They are scattered among $N$ different cities and would like to build a highway network such that there is a path between any two cities. There are $M$ different potential highway plans that they are considering. The $i^{th}$ highway plan connects cities $a_i$ and $b_i$, with a bidirectional highway that has a durability of $d_i$, and takes $t_i$ time to complete.

Each highway in the network must have a minimum durability, and a maximum amount of time to completion. Since the squirrels are indecisive, they will ask you $Q$ questions. Each question is in the form of two integers, $x_j$, and $y_j$. They want you to determine whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least $x_j$, and each highway taking no longer than $y_j$ time to complete.

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

$2\le N\le 100000$
$1\le M\le 300000$
$1\le Q\le 300000$
$1\le a_i,b_i\le N$ for all $1\le i\le M$
$1\le d_i,t_i\le {10}^9$ for all $1\le i\le M$
$1\le x_j,y_j\le {10}^9$ for all $1\le j\le Q$

Subtask 1 [9%]

$2\le N\le 1000$
$1\le M\le 3000$
$1\le Q\le 3000$

Subtask 2 [40%]

$2\le N\le 3000$
$1\le M\le 9000$

Subtask 3 [51%]

No additional constraints.

Input Specification

The first line of input contains $3$ integers, $N$, $M$, and $Q$, representing the number of cities in the squirrel nation, the number of potential highway plans, and the number of questions they will ask you.

The next $M$ lines describe the highway plans. The $i^{th}$ line contains $4$ integers, $a_i$, $b_i$, $d_i$, $t_i$, indicating that the $i^{th}$ plan connects cities $a_i$ and $b_i$ with a bidirectional highway that has a durability of $d_i$, and takes $t_i$ time to complete.

The next $Q$ lines describe the questions the squirrels will ask. The $j^{th}$ line contains $2$ integers, $x_j$, $y_j$, indicating that the $j^{th}$ question is asking whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least $x_j$, and each highway taking no longer that $y_j$ time to complete.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output $Q$ lines. The $j^{th}$ line should contain the answer to the $j^{th}$ query. If there is a way to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least $x_j$, and each highway taking no longer than $y_j$ time to complete, then output YES. Otherwise, output NO.

Sample Input 1

3 3 2
1 2 10 5
2 3 5 3
3 1 8 9
4 7
6 8

Sample Output 1

YES
NO

Sample Explanation 1

For the first question, the first and second highway plans can be built to satisfy the requirements.

For the second question, there is no possible way to build a highway network that satisfies all requirements.