409970: GYM103870 O Highways

Timothy travels between lattice points on a coordinate plane, with $$$Y \in$$$ {$$$1,2...N$$$} and $$$X \in$$$ {$$$1,2...M$$$}. He can freely move up and down across Y coordinates, but cannot move freely left and right across X coordinates. However, there are $$$K$$$ roads available to him, each of which spans from $$$(x_a, y_r)$$$ to $$$(x_b, y_r)$$$ where $$$x_a \leq x_b$$$, and allows him to move freely between any points $$$(x_i, y_r)$$$ and $$$(x_j, y_r)$$$ where $$$x_a \leq x_i$$$, $$$x_j \leq x_b$$$. We have to answer $$$Q$$$ queries, each of which asks if it's possible to travel from $$$(A, B)$$$ to $$$(C, D)$$$, traveling only across $$$y$$$ coordinates between $$$min(B, D)$$$ and $$$max(B, D)$$$ inclusive (so he may use roads with y-coordinate $$$B$$$ or $$$D$$$).

The first line contains the integers $$$N$$$ ($$$1 \leq N \leq 10^9$$$), $$$M$$$ ($$$1 \leq M \leq 2 \cdot 10^5$$$), $$$K$$$ $$$(1 \leq K \leq 2 \cdot 10^5)$$$, and $$$Q$$$ ($$$1 \leq Q \leq 2\cdot 10^5$$$) respectively.

The next $$$K$$$ lines denote each of the roads with three integers $$$x_a$$$, $$$x_b$$$, and $$$y_r$$$ respectively ($$$1 \leq x_a \leq x_b \leq M$$$, $$$1 \leq y_r \leq N$$$).

The final $$$Q$$$ lines each denote a query with the integers $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ ($$$B \neq D$$$, $$$1\leq A,C \leq M$$$, $$$1\leq B,D \leq N$$$).

Test cases 1-5: $$$N,$$$ $$$M,$$$ $$$K,$$$ $$$Q \leq 2000$$$

Test cases 6-20: No further restrictions

$$$Q$$$ lines of output where the $$$i$$$'th line is a "YES" if Timothy can reach his destination in the $$$i$$$'th query, and a "NO" if he cannot.

10 5 2 2
1 2 2
2 3 1
1 1 3 3
4 3 2 1

YES
NO

On the first query note that Timothy can move up to $$$(1, 2)$$$, then take the first road to $$$(2, 2)$$$. Then he can move down to $$$(2, 1)$$$, use the second road to move to $$$(3, 1)$$$, and from there move up to his destination at $$$(3, 3)$$$. On the second query note that Timothy is only able to move up and down and therefore not able to make it from $$$(4, 3)$$$ to $$$(2, 1)$$$.

$$$-------------------------------------------------$$$

Idea: Timothy

Preparation: Timothy, Bossologist

Occurences: Advanced 7