Big Table

Mirko and Slavko are always playing some game. They got bored of every existing one, so they decided to invent their own. Mirko imagines a large table of single-digit numbers and writes it down, and Slavko has to answer questions of the form "What is the sum of the numbers in this rectangle?" as fast as he can.

So that Mirko does not have to write out every number of the imagined table, the two agreed on the following. Each row of the table is built by concatenating the row's base period many times and then discarding elements from the end until the row is exactly as wide as the table.

The first line contains $R$ and $S$ ($1 \le R, S \le 100\,000$), the number of rows and the number of columns of the table.

The next $R$ lines contain the base periods of the rows, from the top row down. Each period consists of at most $\min(S, 100)$ digits from 0 to 9, written one after another without spaces.

The next line contains $Q$ ($1 \le Q \le 100\,000$), the number of questions Slavko has to answer.

Each of the following $Q$ lines contains four integers $r_1, s_1, r_2, s_2$ ($1 \le r_1 \le r_2 \le R$ and $1 \le s_1 \le s_2 \le S$) that describe a rectangle in which Slavko has to find the sum of the numbers. $r_1$ and $s_1$ give the top-left cell of the rectangle (row $r_1$, column $s_1$), and $r_2$ and $s_2$ give the bottom-right cell. Rows are numbered 1 to $R$ from top to bottom, and columns are numbered 1 to $S$ from left to right.

Print $Q$ lines with Slavko's answers in the order of the questions, exactly one number per line.

The periods in the first sample input describe this table:

1111111111
0404040404
1231231231
9898989898

Slavko has to answer a single question, which asks for the sum of all numbers in the table. That sum is 134.