Score : $600$ points
There is a complex composed of $N$ $10^9$-story skyscrapers. The skyscrapers are numbered $1$ to $N$, and the floors are numbered $1$ to $10^9$.
From any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.
Additionally, there are $M$ elevators. The $i$-th elevator runs between Floor $B_i$ and Floor $C_i$ of Skyscraper $A_i$. With this elevator, one can get from Floor $x$ to Floor $y$ of Skyscraper $A_i$ in $|x-y|$ minutes, for every pair of integers $x,y$ such that $B_i \le x,y \le C_i$.
Answer the following $Q$ queries.
Input is given from Standard Input in the following format:
$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$
Each query is in the following format:
$X_i$ $Y_i$ $Z_i$ $W_i$
Print $Q$ lines. The $i$-th line should contain -1
if, for $\mathrm{query}_i$, the destination is unreachable; otherwise, it should contain the minimum number of minutes needed to get there.
3 4 3 1 2 10 2 3 7 3 9 14 3 1 3 1 3 3 14 3 1 2 7 1 100 1 101
12 7 -1
For the $1$-st query, you can get to the destination in $12$ minutes as follows.
For the $3$-rd query, the destination is unreachable, so -1
should be printed.
1 1 1 1 1 2 1 1 1 2
1