Shortest Time in a Staircase Building

The teaching building of Xiao \(X\) School is a building with \(H\) floors. We model the building as a grid with \(H\) rows (floors) and \(M\) columns (positions on each floor). Students can freely move horizontally on the same floor (each move between adjacent cells costs \(1\) second), but to move vertically (i.e. change floors) they must use a staircase.

A staircase in a column connects a contiguous segment of floors. In each column there is at most one staircase. In column \(c\), if a staircase exists, it is given by two integers \(L_c\) and \(R_c\) (with \(L_c < R_c\)), meaning that the staircase occupies all cells \((r,c)\) for \(L_c \le r \le R_c\). A student can move vertically (up or down by one floor, costing 1 second each step) in column \(c\) if and only if his current floor and the adjacent floor are both within the staircase’s range \([L_c, R_c]\).

There are \(T\) queries. In each query a student is at a starting cell \((s, y_1)\) and wants to go to a destination cell \((t, y_2)\). Note that if \(s=t\) the student can simply move horizontally and spend \(|y_1-y_2|\) seconds. Otherwise, in order to change floors the student must first move horizontally on floor \(s\) to some column \(c\) such that a staircase exists in that column and \(s\) is in \([L_c, R_c]\). Then, while staying in column \(c\), the student climbs (or descends) from floor \(s\) to floor \(t\), which is possible only if \(t\) is also in \([L_c, R_c]\). Finally, on floor \(t\) the student moves horizontally from column \(c\) to \(y_2\). The total time is thus \[ |y_1 - c| + |s - t| + |y_2 - c|. \]

If there is no column \(c\) such that the staircase in that column covers both floors \(s\) and \(t\), then the destination is unreachable and you should output -1.

Your task is: for each query, compute the minimum time required to go from \((s, y_1)\) to \((t, y_2)\) under the above rules.

inputFormat

The input begins with a line containing three integers \(H\), \(M\) and \(T\): the number of floors, the number of columns and the number of queries, respectively.

The next line contains \(2\times M\) integers. For each column \(c\) from \(1\) to \(M\), two integers \(L_c\) and \(R_c\) are given. If there is no staircase in column \(c\), then both \(L_c\) and \(R_c\) will be given as -1; otherwise, it is guaranteed that \(L_c < R_c\) and the staircase in that column connects all floors \(r\) with \(L_c \le r \le R_c\).

Each of the following \(T\) lines contains four integers: \(s\), \(y_1\), \(t\) and \(y_2\), indicating a query where the student starts at floor \(s\), column \(y_1\) and wants to reach floor \(t\), column \(y_2\).

outputFormat

For each query, output a single integer: the minimum time required to travel from \((s, y_1)\) to \((t, y_2)\) under the movement rules described. If it is impossible to reach the destination, output -1.

sample

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

7
1
6
6