/* paiza POH! vol.2
* result:
* http://p...content-available-to-author-only...a.jp/poh/paizen/result/f6f0fe8ff017d992643851b61e32cb4c
* author: Leonardone @ NEETSDKASU
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
{
Paiza.getInstance().resolve(new MyResolver());
}
}
{
int[][] table = null;
int[][] cache = null;
@Override
public void setHome(Paiza.Home home) {
super.setHome(home);
table = new int[home.getH() + 1][home.getW() + 1];
cache = new int[home.getH() + 1][home.getW() + 1];
int[] space2top = new int[home.getW()];
for (int y = 0; y < home.getH(); y++) {
for (int x = 0; x < home.getW(); x++) {
if (home.isSpace(x, y)) {
space2top[x]++;
int s = space2top[x];
int t = 1;
for (int i = x; i >= 0 && space2top[i] > 0; i--) {
if (space2top[i] < s) {
s = space2top[i];
}
table[s][t]++;
t++;
}
} else {
space2top[x] = 0;
}
}
}
} // setHome()
@Override
public int resolve(Paiza.Widget widget) {
int s = widget.getS();
int t = widget.getT();
if (s > home.getH() || t > home.getW()) {
return 0;
}
if (cache[s][t] > 0) {
return cache[s][t] - 1;
}
int count = 0;
for (int i = s; i <= home.getH(); i++) {
count += table[i][t];
}
cache[s][t] = count + 1;
return count;
} // resolve()
}
final class Paiza
{
{
protected Paiza.Home home;
public void setHome(Paiza.Home home) {
this.home = home;
}
public abstract int resolve(Paiza.Widget widget);
}
public static Paiza getInstance
() throws java.
lang.
Exception { if (paiza == null) {
paiza = new Paiza();
}
return paiza;
}
public void resolve
(Resolver resolver
) { init(resolver);
for (Widget widget : widgets) {
answer(resolver.resolve(widget));
}
flush();
}
public final class Home
{
private final int H;
private final int W;
private int[][] display;
private Home(int H, int W) {
this.H = H;
this.W = W;
display = new int[H][W];
}
private void setDisplay
(int x,
int y,
int e
) throws java.
lang.
Exception { if (x < 0 || x >= W) {
}
if (y < 0 || y >= H) {
}
if (e != 0 && e != 1) {
}
display[y][x] = e;
}
public int getH() {
return H;
}
public int getW() {
return W;
}
public boolean isSpace(int x, int y) {
if (x < 0 || y < 0 || x >= W || y >= H) {
return false;
}
return display[y][x] == 0;
}
}
public final class Widget
{
private final int s;
private final int t;
private Widget(int s, int t) {
this.s = s;
this.t = t;
}
public int getS() {
return s;
}
public int getT() {
return t;
}
}
private static Paiza paiza = null;
private Home home;
private ArrayList<Widget> widgets;
String[] hw
= in.
readLine().
split(" "); for (int y = 0; y < home.getH(); y++) {
for (int x = 0; x < home.getW(); x++) {
home.setDisplay(x, y, (int)(line.charAt(x) - '0'));
}
}
int N
= Integer.
parseInt(in.
readLine()); widgets = new ArrayList<Widget>(N);
for (int i = 0; i< N; i++) {
String[] st
= in.
readLine().
split(" "); widgets.
add(new Widget
(Integer.
parseInt(st
[0]),
Integer.
parseInt(st
[1]))); }
}
private StringBuilder output = null;
private static final String NEWLINE
= System.
getProperty("line.separator");
resolver.setHome(home);
output = new StringBuilder(widgets.size() * 6);
}
private void answer(int count) {
output.append(count);
output.append(NEWLINE);
}
private void flush() {
}
}