Elevators

AtCoder

IDabc254_g

Time6000ms

Memory256MB

Difficulty—

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. * 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. ## Constraints * $1 \le N,M,Q \le 2 \times 10^5$ * $1 \le A_i \le N$ * $1 \le B_i < C_i \le 10^9$ * $1 \le X_i,Z_i \le N$ * $1 \le Y_i,W_i \le 10^9$ * All values in input are integers. ## 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$ $\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$ [samples]

Samples

Input #1

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

Output #1

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.

Input #2

1 1 1
1 1 2
1 1 1 2

Output #2

API Response (JSON)

{
  "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 skybri...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments