Problem 4490: tenis

Vrei tenis? ...
Sun Tzu

Cerință

Se dă un șir, $a$ , de $n$ dreptunghiuri în plan, descrise prin colțurile stânga-jos și dreapta-sus. Se dau $q$ interogări de forma $(l, r)$ cu semnificația: dacă considerăm doar dreptunghiurile $a[l \dots r]$ , este reuniunea lor un dreptunghi perfect? Reuniunea este un dreptunghi perfect dacă este exact un dreptunghi, fără "goluri”, și dacă oricare două dintre dreptunghiurile care o formează nu se suprapun (pot avea în comun doar puncte de pe laturi).

Date de intrare

Pe prima linie se găsesc numerele $n$ și $q$ .
Următoarele $n$ linii descriu elementele șirului $a$ . Un dreptunghi este descris prin patru numere $x_0, y_0, x_1, y_1$ , unde $(x_0, y_0)$ este colțul stânga-jos al dreptunghiului, iar $(x_1, y_1)$ este colțul dreapta-sus.
Următoarele $q$ linii descriu interogările, iar fiecare conține câte două numere, $l$ și $r$ .

Date de ieșire

Se vor afișa $q$ linii, iar pe linia $i$ se va afla răspunsul pentru interogarea $i$ : "YES” dacă reuniunea dreptunghiurilor este un dreptunghi perfect, respectiv "NO” în caz contrar.

Restricții și precizări

$1 \leq n, q \leq 500 \ 000$
$0 \leq x_0 < x_1 \leq 10^9$
$0 \leq y_0 < y_1 \leq 10^9$
$1 \leq l \leq r \leq n$
Pentru teste în valoare de $29$ de puncte, $1 \leq n, q \leq 100$ și $x_1, y_1 \leq 10^6$ .
Pentru teste în valoare de alte $49$ de puncte, $1 \leq n, q \leq 50 \ 000$ .

Exemplul 1

stdin

stdout

YES
NO
NO

Explicație

Pentru prima întrebare, dreptunghiurile 1–4 acoperă exact dreptunghiul [0, 14] × [0, 7], fără să se suprapună.

 y
 7 ┌───────────────────┬───────┐
   │         3         │       │
 4 ├───────────┬───────┤   4   │
   │     1     │   2   │       │
 0 └───────────┴───────┴───────┘
   0           6      10      14  x

Pentru a doua, fără dreptunghiul 1 zona [0, 6] × [0, 4] rămâne neacoperită. Pentru a treia, dreptunghiurile 4 și 5 se suprapun pe [10, 12] × [2, 5].

tenis