Problem Description

You are given $n$ Boolean variables and $m$ constraints. Let $s_i$ be the value of variable $i$. The $i$-th constraint is of the form: if $s_{u_i}$ is $x_i$, then $s_{v_i}$ must be $y_i$; at the same time, if $s_{v_i}$ is $y_i$, then $s_{u_i}$ must be $x_i$.

There are $q$ queries in total. Each query gives an interval $l,r$. Find the minimum number of continuous segments to partition $[l,r]$ into, such that the constraints within each segment have at least one legal solution. If no legal solution can be obtained no matter what, output -1.

Input Format

The first line contains three integers $n,m,q$.
The next $m$ lines each contain four integers, representing $u_i,x_i,v_i,y_i$.
The next $q$ lines each contain two integers, representing $l_i,r_i$.

Output Format

For each query, output one integer as the answer. If it is impossible to get an answer, output -1.

3 4 2
1 0 2 0
1 1 3 0
3 0 2 0
1 1 2 1
1 3
3 4

2
1

4 5 3
1 1 2 1
2 0 3 0
4 1 1 0
2 1 4 0
4 0 3 0
1 4
2 5
3 5

1
2
1

Hint

Sample Explanation 1
For the first query, it can be split into two segments: $[1,2]$ and $3$.
For the second query, it is one segment: $[3,4]$.

Sample Explanation 2
For the first query, it is one segment: $[1,4]$.
For the second query, it can be split into two segments: $[2,3]$ and $[4,5]$.
For the third query, it is one segment: $[3,5]$.

For $100\%$ of the testdata, $1\le n\le10^5,1\le m\le6\times10^5,1\le q\le10^6,1\le u,v\le n,1\le l\le r\le m,x,y\in \{0,1\}$.

Translated by ChatGPT 5