{"problem":{"name":"Elevators","description":{"content":"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 skybri","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc254_g"},"statements":[{"statement_type":"Markdown","content":"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$.\nFrom any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.\nAdditionally, 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$.\nAnswer the following $Q$ queries.\n\n*   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.\n\n## Constraints\n\n*   $1 \\le N,M,Q \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le N$\n*   $1 \\le B_i < C_i \\le 10^9$\n*   $1 \\le X_i,Z_i \\le N$\n*   $1 \\le Y_i,W_i \\le 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n$\\mathrm{query}_1$\n$\\mathrm{query}_2$\n$\\vdots$\n$\\mathrm{query}_Q$\n\nEach query is in the following format:\n\n$X_i$ $Y_i$ $Z_i$ $W_i$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc254_g","tags":[],"sample_group":[["3 4 3\n1 2 10\n2 3 7\n3 9 14\n3 1 3\n1 3 3 14\n3 1 2 7\n1 100 1 101","12\n7\n-1\n\nFor the $1$\\-st query, you can get to the destination in $12$ minutes as follows.\n\n*   Use Elevator $1$ to get from Floor $3$ to Floor $9$ of Skyscraper $1$, in $6$ minutes.\n*   Use the skybridge on Floor $9$ to get from Skyscraper $1$ to Skyscraper $3$, in $1$ minute.\n*   Use Elevator $3$ to get from Floor $9$ to Floor $14$ of Skyscraper $3$, in $5$ minutes.\n\nFor the $3$\\-rd query, the destination is unreachable, so `-1` should be printed."],["1 1 1\n1 1 2\n1 1 1 2","1"]],"created_at":"2026-03-03 11:01:14"}}