/* paiza POH! vol.2
* result:
* http://p...content-available-to-author-only...a.jp/poh/paizen/result/bf7480d30634518ea96a73ad395b744e
* author: Leonardone @ NEETSDKASU
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
static int[] sp = new int[30300];
static int[] tb = new int[30300];
static int[] ca = new int[30300];
{
String[] hw
= in.
readLine().
split(" "); int H
= Integer.
parseInt(hw
[0]); // ホーム画面縦の区画数 int W
= Integer.
parseInt(hw
[1]); // ホーム画面横の区画数
int[] space2right = sp;
int[] table = tb;
int[] cache = ca;
int y, x, j ,i, s, t;
int count;
for (y = 0; y < H; y++)
{
line = in.readLine();
count = 0;
for (x = W - 1; x >= 0; x--)
{
if (line.charAt(x) == '0')
{
count++;
}
else
{
count = 0;
}
space2right[y * 301 + x] = count;
}
}
j = 0;
for (y = 0; y < H; y++)
{
for (x = 0; x < W; x++)
{
if (space2right[j + x] == 0)
{
continue;
}
s = 301;
t = space2right[j + x];
for (i = y; i < H && space2right[i * 301 + x] > 0; i++)
{
if (space2right[i * 301 + x] < t)
{
t = space2right[i * 301 + x];
}
table[s + t]++;
s += 301;
}
}
j += 301;
}
int N
= Integer.
parseInt(in.
readLine()); // ウィジェット数 StringBuilder output = new StringBuilder(N * 6);
for (i = 0; i < N; i++)
{
hw = in.readLine().split(" ");
s
= Integer.
parseInt(hw
[0]); // ウィジェットの縦サイズ t
= Integer.
parseInt(hw
[1]); // ウィジェットの横サイズ
count = 0;
if (s <= H && t <= W)
{
y = s * 301;
x = y + t;
if (cache[x] > 0)
{
count = cache[x] - 1;
}
else
{
for (j = t; j <= W; j++)
{
count += table[y + j];
}
cache[x] = count + 1;
}
}
output.append(count);
output.append('\n');
}
} // end of main(String[])
}
LyogcGFpemEgUE9IISB2b2wuMgogKiByZXN1bHQ6CiAqIGh0dHA6Ly9wLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLmpwL3BvaC9wYWl6ZW4vcmVzdWx0L2JmNzQ4MGQzMDYzNDUxOGVhOTZhNzNhZDM5NWI3NDRlCiAqIGF1dGhvcjogTGVvbmFyZG9uZSBAIE5FRVRTREtBU1UKICovCmltcG9ydCBqYXZhLnV0aWwuKjsKaW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgamF2YS5pby4qOwoKY2xhc3MgTWFpbgp7CglzdGF0aWMgaW50W10gc3AgPSBuZXcgaW50WzMwMzAwXTsKCXN0YXRpYyBpbnRbXSB0YiA9IG5ldyBpbnRbMzAzMDBdOwoJc3RhdGljIGludFtdIGNhID0gbmV3IGludFszMDMwMF07CgkKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCUJ1ZmZlcmVkUmVhZGVyIGluID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKAoJCQluZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CgkJCgkJU3RyaW5nW10gaHcgPSBpbi5yZWFkTGluZSgpLnNwbGl0KCIgIik7CgkJaW50IEggPSBJbnRlZ2VyLnBhcnNlSW50KGh3WzBdKTsgLy8g44Ob44O844Og55S76Z2i57im44Gu5Yy655S75pWwCgkJaW50IFcgPSBJbnRlZ2VyLnBhcnNlSW50KGh3WzFdKTsgLy8g44Ob44O844Og55S76Z2i5qiq44Gu5Yy655S75pWwCgkJCgkJaW50W10gc3BhY2UycmlnaHQgPSBzcDsKCSAJaW50W10gdGFibGUgPSB0YjsKCQlpbnRbXSBjYWNoZSA9IGNhOwoJCQoJCWludCB5LCB4LCBqICxpLCBzLCB0OwoJCVN0cmluZyBsaW5lOwoJCWludCBjb3VudDsKCQkKCQlmb3IgKHkgPSAwOyB5IDwgSDsgeSsrKQoJCXsKCQkJbGluZSA9IGluLnJlYWRMaW5lKCk7CgkJCWNvdW50ID0gMDsKCQkJZm9yICh4ID0gVyAtIDE7IHggPj0gMDsgeC0tKQoJCQl7CgkJCQlpZiAobGluZS5jaGFyQXQoeCkgPT0gJzAnKQoJCQkJewoJCQkJCWNvdW50Kys7CgkJCQl9CgkJCQllbHNlCgkJCQl7CgkJCQkJY291bnQgPSAwOwoJCQkJfQoJCQkJc3BhY2UycmlnaHRbeSAqIDMwMSArIHhdID0gY291bnQ7CgkJCX0KCQl9CgkJCgkJaiA9IDA7CgkJZm9yICh5ID0gMDsgeSA8IEg7IHkrKykKCQl7CgkJCWZvciAoeCA9IDA7IHggPCBXOyB4KyspCgkJCXsKCQkJCWlmIChzcGFjZTJyaWdodFtqICsgeF0gPT0gMCkKCQkJCXsKCQkJCQljb250aW51ZTsKCQkJCX0KCQkJCXMgPSAzMDE7CgkJCQl0ID0gc3BhY2UycmlnaHRbaiArIHhdOwoJCQkJZm9yIChpID0geTsgaSA8IEggJiYgc3BhY2UycmlnaHRbaSAqIDMwMSArIHhdID4gMDsgaSsrKQoJCQkJewoJCQkJCWlmIChzcGFjZTJyaWdodFtpICogMzAxICsgeF0gPCB0KQoJCQkJCXsKCQkJCQkJdCA9IHNwYWNlMnJpZ2h0W2kgKiAzMDEgKyB4XTsKCQkJCQl9CgkJCQkJdGFibGVbcyArIHRdKys7CgkJCQkJcyArPSAzMDE7CgkJCQl9CgkJCX0KCQkJaiArPSAzMDE7CgkJfQoJCQoJCWludCBOID0gSW50ZWdlci5wYXJzZUludChpbi5yZWFkTGluZSgpKTsgLy8g44Km44Kj44K444Kn44OD44OI5pWwCgkJU3RyaW5nQnVpbGRlciBvdXRwdXQgPSBuZXcgU3RyaW5nQnVpbGRlcihOICogNik7CgoJCWZvciAoaSA9IDA7IGkgPCBOOyBpKyspCgkJewoJCQlodyA9IGluLnJlYWRMaW5lKCkuc3BsaXQoIiAiKTsKCQkJcyA9IEludGVnZXIucGFyc2VJbnQoaHdbMF0pOyAvLyDjgqbjgqPjgrjjgqfjg4Pjg4jjga7nuKbjgrXjgqTjgroKCQkJdCA9IEludGVnZXIucGFyc2VJbnQoaHdbMV0pOyAvLyDjgqbjgqPjgrjjgqfjg4Pjg4jjga7mqKrjgrXjgqTjgroKCQkJCgkJCWNvdW50ID0gMDsKCQkJaWYgKHMgPD0gSCAmJiB0IDw9IFcpCgkJCXsKCQkJCXkgPSBzICogMzAxOwoJCQkJeCA9IHkgKyB0OwoJCQkJaWYgKGNhY2hlW3hdID4gMCkKCQkJCXsKCQkJCQljb3VudCA9IGNhY2hlW3hdIC0gMTsKCQkJCX0KCQkJCWVsc2UKCQkJCXsKCQkJCQlmb3IgKGogPSB0OyBqIDw9IFc7IGorKykKCQkJCQl7CgkJCQkJCWNvdW50ICs9IHRhYmxlW3kgKyBqXTsKCQkJCQl9CgkJCQkJY2FjaGVbeF0gPSBjb3VudCArIDE7CgkJCQl9CgkJCX0KCgkJCW91dHB1dC5hcHBlbmQoY291bnQpOwoJCQlvdXRwdXQuYXBwZW5kKCdcbicpOwoJCX0KCQkKCQlTeXN0ZW0ub3V0LnByaW50KG91dHB1dCk7CgkJCgl9IC8vIGVuZCBvZiBtYWluKFN0cmluZ1tdKQoJCn0K