E. Тэрэгнүүд ба тэгш өнцөгтүүд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарпуст $n × m$ хэмжээтэй шатрын хөлөг ба түүн дээр байрласан $k$ ширхэг тэрэг байлаа. Поликарпус эдгээрт тохирсон тоглоомын дүрэм зохиохоор шийдэв. Тэгээд аль хэдийн хөлөг дээр $q$ ширхэг стратегийн хувьд чухал гэж үзсэн тэгш өнцөгт талбайнуудыг тэмдэглэсэн байв. Тэр хэсгүүд аюулгүй байх ёстой. Поликарпусын хэлж байгаагаар стратегийн хувьд чухал тэгш өнцөгт нь түүн дээр байрлах тэрэгнүүд уг тэгш өнцөгтийн хоосон нүд бүрийг хамгаалж байвал аюулгүй байх болно. Харин уг тэгш өнцөгтөөс гадна байрлах тэрэг уг тэгш өнцөгтөд нөлөө үзүүлэхгүй. Тэрэгнүүдийн байрлал бэхлэгдсэн ба өөрчлөгдөхгүй. Сануулж хэлэхэд тэрэг нь өөрөөсөө хэвтээ болон босоо чиглэлд байрлах дараалсан хоосон нүднүүдийг хамгаалж байдаг. Поликарпуст бүх стратегийн тэгш өнцөгтүүд аюулгүй эсэхийг мэдэхэд туслаарай.

Оролт

Эхний мөрөнд хөлгийн хэмжээс, тэрэгний тоо болон стратегийн тэгш өнцөгтийн тоог илэрхийлэх $n$, $m$, $k$, $q$ ($1 ≤ n, m ≤ 100 000$, $1 ≤ k, q ≤ 200 000$) тоонууд байна. Хөлгийн нүднүүдийг хөндлөнгөөр $1$-ээс $n$ хүртэл, босоогоор $1$-ээс $m$ хүртэл дугаарлана. Дараагийн $k$ мөр бүрт "$x$ $y$" ($1 ≤ x ≤ n$, $1 ≤ y ≤ m$) гэсэн хос тоо байх ба тэрэгнүүдийн байрлалыг илэрхийлнэ. Тэрэг бүр ялгаатай нүдэнд байрлана. Дараагийн $q$ мөр бүрт стратегийн тэгш өнцөгтүүдийн байрлалыг илэрхийлэх "$x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$" ($1 ≤ x_{1} ≤ x_{2} ≤ n$, $1 ≤ y_{1} ≤ y_{2} ≤ m$) тоонууд өгөгдөнө. Харгалзах тэгш өнцөгт нь $x_{1} ≤ x ≤ x_{2}$, $y_{1} ≤ y ≤ y_{2}$ нөхцөлийг хангах бүх $(x, y)$ нүднээс тогтоно. Стратегийн тэгш өнцөгтүүд хоорондоо огтлолцож болно.

Гаралт

Хариуг $q$ мөрөнд хэвлэ. Стратегийн тэгш өнцөгт бүрийн хувьд аюулгүй бол "YES", бусад тохиолдолд "NO" гэж хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4 3 3 3
1 1
3 2
2 3
2 3 2 3
2 1 3 3
1 2 2 3
Гаралт
YES
YES
NO

Тэмдэглэл

Жишээг зургаар дүрсэлбэл:

$(1, 2)$ нүд хамгаалагдаагүй тул сүүлийн тэгш өнцөгтийн хувьд "NO" гэж хэвлэнэ.

Сэтгэгдлүүдийг ачааллаж байна...