Segmented Range Query

You are given a sequence of n data points, along with two integers k and q.

The task is to:

1. Divide the data points into k segments. The segments are formed in order. Each segment gets a size of \(\lfloor n/k \rfloor\) and the first \(n\,\%\,k\) segments get one extra element.
2. Sort each segment individually. Then flatten the segments into a single list by concatenating them in the original segment order.
3. Compute the prefix sums for the flattened list. Formally, if the flattened list is \(a_1, a_2, \dots, a_n\), then define the prefix sum array \(P\) as: \[ P[0]=0,\quad P[i]=a_1+a_2+\cdots+a_i \quad (1\le i\le n). \]
4. Answer q range sum queries. Each query is given by two integers \(l\) and \(r\) (1-indexed) and the answer is \(P[r]-P[l-1]\).

Note: The query indices use 1-based indexing. All formulae are expressed in \(\LaTeX\) format.

inputFormat

The input is read from stdin and has the following format:

• The first line contains three integers: \(n\) (number of data points), \(k\) (number of segments), and \(q\) (number of queries).
• The second line contains \(n\) space-separated integers representing the data points.
• Each of the next \(q\) lines contains two integers \(l\) and \(r\), representing a query where you must compute the sum of data points from index \(l\) to \(r\) in the processed array.

outputFormat

For each query, output the sum on a separate line to stdout.

## sample

6 3 2
5 2 9 1 7 3
1 4
2 6

17
25

</p>