Consistent Boolean Segmentation

You are given n boolean variables and m bidirectional constraints. The variables are denoted by \(s_1, s_2, \ldots, s_n\), and each constraint is of the following form:

"If \(s_{u_i}\) is \(x_i\) then \(s_{v_i}\) must be \(y_i\), and if \(s_{v_i}\) is \(y_i\) then \(s_{u_i}\) must be \(x_i\)."

This condition can be reformulated in latex as:

\[ s_{u_i} = x_i \iff s_{v_i} = y_i, \quad 1 \le i \le m. \]

You are also given q queries. In each query an interval \([l, r]\) (1-indexed over the constraints) is provided. Your task is to partition the interval \([l, r]\) into the minimum number of contiguous segments such that for every segment, the set of constraints within that segment is consistent (i.e. there exists an assignment of the boolean variables which satisfies all the constraints in that segment). If it is impossible to partition \([l,r]\) so that every segment is consistent, output -1.

Note: A constraint of the form \(s_u = x \iff s_v = y\) implies that if \(x = y\) then the constraint enforces \(s_u = s_v\), and if \(x \neq y\) then it enforces \(s_u \neq s_v\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) representing the number of boolean variables, the number of constraints, and the number of queries respectively.

Then \(m\) lines follow, each contains four integers \(u_i\), \(x_i\), \(v_i\), \(y_i\) where \(u_i\) and \(v_i\) (1-indexed) denote the variable indices, and \(x_i, y_i \in \{0,1\}\).

Then \(q\) lines follow, each containing two integers \(l\) and \(r\) (1-indexed) representing a query over the constraints indices.

outputFormat

For each query, print a single line containing the minimum number of contiguous segments into which the given interval can be partitioned such that each segment's constraints are consistent. If it is impossible, print -1.

sample

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

1
2
3