C. Шинэ жил ба даалуу

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

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

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

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

Тэд "он жилүүд бол даалуутай адил, нэг нэгнийхээ араас нуран унаж байдаг" гэж хэлдэг.Гэхдээ он жил ганц торонд багтана гэж үү? Би тэгж бодохгүй байна.

Лимак бол тоглох дуртай нэгэн бяцхан туйлын баавгай юм.Тэрээр саяхан $h$ ширхэг мөр болон $w$ ширхэг багана бүхий тэгш өнцөгт хэлбэртэй тортой болжээ.Нүд бүр нь квадрат хэлбэртэй ба хоосон ('$.$'гэж тэмдэглэнэ) эсвэл хориотой ('$#$' гэж тэмдэглэнэ) гэсэн нүднүүд байх аж.Мөрүүд нь дээрээс доош хүртэл $1$-ээс $h$ хүртэл дугаарлагдсан ба баганууд нь зүүнээс баруун хүртэл $1$-ээс $w$ хүртэл дугаарлагдсан байна.

Мөн, Лимак-д ганц даалуу байв.Тэрээр үүнийгээ торныхоо хаа нэгтээ тавихыг хүсэж байв.Даалуу нь нэг мөр эсвэл нэг баганад байрлалтай яг зэрэгцээ 2 нүдний байрлалыг эзлэх юм.Тэдгээр зэргэлдээ нүднүүд нь 2 уулаа заавал хоосон байх ба торны дотор байх ёстой юм.

Лимак илүү их хөгжилтэй байх хэрэгтэй байгаа ба иймд тэрээр хэсэг асуултыг эргэцүүлж бодохоор болжээ.Асуулт бүрийн хувьд тэрээр нэгэн тэгш өнцөгт сонгох бөгөөд нийт хэчнээн янзаар уг тэгш өнцөгт дотор даалууг байрлуулж болохыг гайхав?

Оролт

Эхний мөрөнд харгалзан мөр болон баганын тоог илэрхийлэх 2 бүхэл тоо $h$ болон $w$ ($1 ≤ h, w ≤ 500$) өгөгдөнө.

Дараагийн $h$ мөрөнд торыг дүрсэлнэ.Мөр болгонд $w$ урттай тэмдэгт мөр өгөгдөнө.Уг тэмдэгт мөрийн тэмдэгт бүр нь '$.$' эсвэл '$#$' байна -- харгалзан хоосон болон хориотой нүдийг тэмдэглэнэ.

Дараагийн мөрөнд асуултын тоо болох ганц бүхэл тоо $q$ ($1 ≤ q ≤ 100 000$) өгөгдөнө.

Дараагийн $q$ мөрийн мөр болгонд $i$-дахь асуултыг илэрхийлэх 4-н бүхэл тоо $r1_{i}$, $c1_{i}$, $r2_{i}$, $c2_{i}$ ($1 ≤ r1_{i} ≤ r2_{i} ≤ h, 1 ≤ c1_{i} ≤ c2_{i} ≤ w$) өгөгдөнө.$r1_{i}$ болон $c1_{i}$ тоонууд нь тэгш өнцөгтийн зүүн дээд нүдний мөр болон багана(харгалзан)-ыг илэрхийлнэ.$r2_{i}$ болон $c2_{i}$ тоонууд нь тэгш өнцөгтийн баруун доод нүдний мөр болон багана(харгалзан)-ыг илэрхийлнэ.

Гаралт

$q$ ширхэг бүхэл тоо хэвлэх ба $i$-дахь тоо нь $i$-дахь тэгш өнцөгтөд нэг даалууг байрлуулах боломжийн тоотой тэнцүү байна.

Орчуулсан: Баатархүү

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

Оролт
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
Гаралт
4
0
10
15
Оролт
7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8
Гаралт
53
89
120
23
0
2

Тэмдэглэл

Доорх улаан хүрээ нь эхний жишээний эхний асуултыг илэрхийлэх юм.Даалуу нь 4 боломжит янзаар байрлаж болно.

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