Maximum Interval Sum on Multiple Sequences

You are given k sequences, each of length n: \(a_{1,1}, a_{1,2}, \dots, a_{1,n}\), \(a_{2,1}, a_{2,2}, \dots, a_{2,n}\), \(\dots\), \(a_{k,1}, a_{k,2}, \dots, a_{k,n}\). You are also given q queries. Each query contains two integers \(l\) and \(r\) representing a range. For each query, compute the value

\[ \max_{1 \le i \le k} \sum_{j=l}^{r} a_{i,j} \]

That is, for the interval \([l, r]\) find the sequence whose sum over that interval is maximum and output that sum.

inputFormat

The first line contains three integers: k (the number of sequences), n (the length of each sequence), and q (the number of queries).

The next k lines each contain n space-separated integers representing the elements of the sequence.

The following q lines each contain two integers l and r representing the query range.

outputFormat

For each query, output a single integer which is the maximum sum over all sequences for the interval \([l, r]\).

Each answer should be printed on a new line.

sample

2 5 3
1 2 3 4 5
5 4 3 2 1
1 3
2 4
1 5

12
9
15