Problem E
Train Tickets

The Stockholm public transport system offers $12$ kinds of tickets for purchase. The $i$’th kind of ticket is valid for exactly $i$ consecutive months. However, they also change the price of every kind of ticket every year.

Katriel has access to the pricing data for the last $N$ years, and is currently studying the complexity of purchasing your tickets in order to minimize costs. More precisely he wants to determine, given an interval of years $a, a + 1, \dots , b$, what the cost is to purchase tickets starting from January in year $a$ that are valid every month to December in year $b$. Can you write a program to determine this?

Input

The first line of input contains the integer $1 \le N \le 30\, 000$, the number of years Katriel has pricing data for. The next $N$ lines contain the pricing data for years $1, 2, \dots , N$, in order. The pricing data for a given year is given as $12$ integers: the prices of the tickets valid for $1, 2, \dots , 12$ months, respectively. All prices are between $0$ and $10\, 000$.

The next line contains the integer $1 \le Q \le 3\, 000$, the number of intervals of years Katriel wishes to compute the price for. The next $Q$ lines contains each of these intervals, given as two integers $1 \le a \le b \le N$ representing the interval $a, a + 1, \dots , b$.

In a given year, a ticket valid for a longer period of time is never cheaper than a ticket valid for a shorter period of time.

Output

For each query $a, b$, output a single line containing the minimum cost to purchase tickets valid during the entire interval, given that the first ticket is bought in January in year $a$.

3
1 2 3 4 5 6 7 8 9 10 11 12
2 3 4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 9 10 11 12 13 14
6
1 1
2 2
3 3
1 2
2 3
1 3

12
13
14
25
27
39