7986: ABC254 —— G - Elevators
[Creator : ]
Description
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≤x,y≤C_i$.
Answer the following Q queries.
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≤x,y≤C_i$.
Answer the following Q queries.
- Determine whether it is possible to get from Floor $Y_i$ of Skyscraper $X_i$ to Floor $W_i$ of Skyscraper $Z_i$, and find the shortest time needed to get there if it is possible.
Input
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$
$⋮$
$A_M\ B_M\ C_M$
query$_1$
query$_2$
$⋮$
query$_Q$
Each query is in the following format:
$X_i\ Y_i\ Z_i\ W_i$
$N\ M\ Q$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$⋮$
$A_M\ B_M\ C_M$
query$_1$
query$_2$
$⋮$
query$_Q$
Each query is in the following format:
$X_i\ Y_i\ Z_i\ W_i$
Output
Print Q lines. The i-th line should contain -1 if, for query$_i$, the destination is unreachable; otherwise, it should contain the minimum number of minutes needed to get there.
Constraints
$1≤N,M,Q≤2×10^5$
$1≤A_i≤N$
$1≤B_i<C_i≤10^9$
$1≤X_i,Z_i≤N$
$1≤Y_i,W_i≤10^9$
All values in input are integers.
$1≤A_i≤N$
$1≤B_i<C_i≤10^9$
$1≤X_i,Z_i≤N$
$1≤Y_i,W_i≤10^9$
All values in input are integers.
Sample 1 Input
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
Sample 1 Output
12
7
-1
For the 1-st query, you can get to the destination in 12 minutes as follows.
- Use Elevator 1 to get from Floor 3 to Floor 9 of Skyscraper 1, in 6 minutes.
- Use the skybridge on Floor 9 to get from Skyscraper 1 to Skyscraper 3, in 1 minute.
- Use Elevator 3 to get from Floor 9 to Floor 14 of Skyscraper 3, in 5 minutes.
For the 3-rd query, the destination is unreachable, so -1 should be printed.
Sample 2 Input
1 1 1
1 1 2
1 1 1 2
Sample 2 Output
1