B. Хөгжилтэйгээр Тэгш өнцөгтийг тоол

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

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

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

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

$nxm$ хэмжээтэй, нүд бүр нь 0 эсвэл 1-с тогтох хүснэгт өгөгдсөн байна. $i$-р мөрний $j$-р элементийг $(i,j)$ гэж тэмдэглье.

"тэгш өнцөгт" гэж $a$, $b$, $c$, $d$ ($1 ≤ a ≤ c ≤ n$, $1 ≤ b ≤ d ≤ m$) гэх оройтой, {$(x, y)$ : $a ≤ x ≤ c$, $b ≤ y ≤ d$} байх нүднүүдийг авч үзье. Хэрвээ бүх нүднүүдийн утга 0 байвал "сайн тэг өнцөгт" гэж нэрлэцгээе.

Та $q$ ширхэг хүсэлтэнд хариулах бөгөөд хүсэлт бүр өгөгдсөн "тэгш өнцөг" дотрох "сайн тэгш өнцөгтийг" тоолно.

Оролт

Эхний мөрөнд $n$, $m$, $q$ тоо өгөгдөнө. ($1 ≤ n, m ≤ 40$, $1 ≤ q ≤ 3·10^5$). Дараагийн $n$ мөр бүрт $m$ тэмдэгт байх бөгөөд үндсэн хүснэгтийг илэрхийлнэ. Баганыг 1-с эхэлж дээрээс дугаарлагдсан, мөрийг 1-с эхэлж зүүн талаас дугаарлагдсан гэж үзээрэй.

Дараагийн $q$ мөрт хүсэлтүүд өгөгдөнө. Хүсэлт бүр "тэгш өнцөгт"-н $a$, $b$, $c$, $d$ ($1 ≤ a ≤ c ≤n$, $1 ≤ b ≤ d ≤m$)-г агуулна.

Гаралт

Бүх хүсэлтэнд хариу болох 1 тоог 1 мөрөнд хэвлэнэ.

Орчуулсан: zoloogg

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

Оролт
5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3
Гаралт
10
1
7
34
5
Оролт
4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7
Гаралт
3
1
16
27
52

Тэмдэглэл

For the first example, there is a $5 × 5$ rectangular grid, and the first, the second, and the third queries are represented in the following image.

  • For the first query, there are $10$ good rectangles, five $1 × 1$, two $2 × 1$, two $1 × 2$, and one $1 × 3$.
  • For the second query, there is only one $1 × 1$ good rectangle.
  • For the third query, there are $7$ good rectangles, four $1 × 1$, two $2 × 1$, and one $3 × 1$.
Сэтгэгдлүүдийг ачааллаж байна...