Define an initial sequence as a sequence where every number is $0$.

An operation is defined as increasing the value of each number in a range of the sequence by $1$, with the constraint that the length of the range cannot exceed $m$.

Given a sequence $a$ of length $n$, where the $i$-th number is $a_i$.

You need to answer $q$ queries. Each query provides $l$ and $r$, and you must determine the minimum number of operations required to transform an initial sequence of length $r-l+1$ into the segment $[l, r]$ of $a$ (i.e., the sequence $a_l, a_{l+1}, \dots, a_r$).

Input

The first line contains three integers $n, m, q$.

The second line contains $n$ integers, where the $i$-th integer is $a_i$.

The next $q$ lines each contain two integers, representing $l$ and $r$.

Output

For each query, output a single integer on a new line representing the minimum number of operations required.

Examples

Input 1

5 4 1
1 1 2 1 1
1 5

Output 1

2

Note 1

An initial sequence of length $5$ is $0$ $0$ $0$ $0$ $0$.

The first operation increases each number in the range $[1, 3]$ (the $1$st, $2$nd, and $3$rd numbers) by $1$. After this operation, the sequence becomes $1$ $1$ $1$ $0$ $0$.

The second operation increases each number in the range $[3, 5]$ (the $3$rd, $4$th, and $5$th numbers) by $1$. After this operation, the sequence becomes $1$ $1$ $2$ $1$ $1$.

Input 2

10 3 3
4 8 1 2 9 7 4 1 3 5
1 10
3 8
5 5

Output 2

22
10
9

Subtasks

• Subtask 1 (1 point): $m=1$.
• Subtask 2 (4 points): $m=n$.
• Subtask 3 (10 points): $n, q \le 300$.
• Subtask 4 (10 points): $n, q \le 5 \times 10^3$.
• Subtask 5 (15 points): $m \le 5$.
• Subtask 6 (15 points): $m \le 100$.
• Subtask 7 (20 points): $n, q \le 5 \times 10^4$.
• Subtask 8 (25 points): No special constraints.

For $100\%$ of the data, it is guaranteed that $1 \le m \le n \le 10^5$, $1 \le q \le 10^5$, $0 \le a_i \le 10^9$, and $1 \le l \le r \le n$.