E. Хурдан яст мэлхий

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

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

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

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

Жон Дойд $n × m$ хэмжээтэй тэгш өнцөгт хүснэгт байжээ. Хүснэгтийн мөрүүд дээрээсээ доош $1$-ээс $n$ хүртэл, баганууд зүүнээс баруун руу $1$-ээс $m$ хүртэл дугаарлагдсан. Мөн $x$ дугаарын мөр болон $y$ дугаарын багануудын огтлолцолд буй нүдийг $(x, y)$ координаттай гэе.

Хүснэгтийн зарим нүд цагаанаар, зарим нь хараар будагдсан. Мөн Жонд зөвхөн цагаан нүдэн дээгүүр явж чадах яст мэлхий байгаа. Яст мэлхий ($x, y$) нүдэн дээр байгаа гэж үзвэл $(x + 1, y)$ ба $(x, y + 1)$ нүднүүдийн аль ч цагаан руу нь явж чадна. Өөрөөр хэлбэл яст мэлхий зөвхөн баруун эсвэл доор байрлах цагаан нүдрүү шилжиж чадна. Мөн яст мэлхий хүснэгтээс гарч чадахгүй.

Түүнчлэн Жонд $q$ хүсэлт байгаа ба хүсэлт бүр $x_{1}, y_{1}, x_{2}, y_{2}$ $(x_{1} ≤ x_{2}$, $y_{1} ≤ y_{2})$ гэсэн дөрвөн тоогоор тодорхойлогдоно. Жон хүсэлт бүрт яст мэлхий $(x_{1}, y_{1})$ нүднээс эхлэн $(x_{2}, y_{2})$ нүдэнд хүрч чадах эсэхийг мэдэхийг хүсчээ.

Оролт

Эхний мөрөнд хүснэгтийн хэмжээг илэрхийлэх $n$, $m$ ($1 ≤ n, m ≤ 500$) бүхэл тоонууд байна.

Дараагийн $n$ мөр бүрт $m$ ширхэг тэмдэгт байх ба тэмдэгт бүр "#" эсвэл "." байна: $i$ дэх мөрний $j$ дэх тэмдэгт "#" бол хүснэгтийн ($i, j$) нүд хар өнгөөр будагдсаныг харин "." бол цагаанаар будагдсаныг илэрхийлнэ.

Дараагийн мөрөнд хүсэлтийн тоог илэрхийлэх $q$ ($1 ≤ q ≤ 6 \cdot 10^{5})$ гэсэн бүхэл тоо байна. Дараагийн $q$ мөр бүрт эхлэл болон төгсгөлийн нүдний координатыг илэрхийлэх $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ ($1 ≤ x_{1} ≤ x_{2} ≤ n$, $1 ≤ y_{1} ≤ y_{2} ≤ m$) гэсэн бүхэл тоонууд зайгаар тусгаарлагдан байна. ($x_{1}, y_{1}$) ба ($x_{2}, y_{2}$) нүднүүд цагаан байхаар өгөгдөнө.

Гаралт

$q$ хүсэлт бүрт хэрэв яст мэлхий нөхцлийг ханган ($x_{1}, y_{1}$) нүднээс ($x_{2}, y_{2}$) нүдрүү очиж чадах бол "Yes", харин чадахгүй бол "No" гэж хэвлэнэ үү. Хариуг хүсэлтүүд өгөгдсөн дарааллаар нь хэвлээрэй.

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

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

Оролт
3 3
...
.##
.#.
5
1 1 3 3
1 1 1 3
1 1 3 1
1 1 1 2
1 1 2 1
Гаралт
No
Yes
Yes
Yes
Yes
Оролт
5 5
.....
.###.
.....
.###.
.....
5
1 1 5 5
1 1 1 5
1 1 3 4
2 1 2 5
1 1 2 5
Гаралт
Yes
Yes
Yes
No
Yes
Сэтгэгдлүүдийг ачааллаж байна...