Road Construction

SciOI City's mayor, Sangryeol, wants to build a new road. The ground where he plans to build it is too bumpy, and compacting the ground alone is expected to take years. The land is a straight strip split into $N$ segments, whose heights may be equal or different. Heights can be negative. The state of the road is given by a sequence $A$ of length $N$, where $A_i$ is the height of the $i$-th segment.

Fortunately, Sangryeol is a wizard who can cast a spell that raises or lowers the heights of $K$ consecutive segments by the same amount. $K$ is fixed.

For example, let $N = 5$, $K = 2$, and the road be as follows.

3 5 6 2 9

If Sangryeol casts a spell that raises the third and fourth segments by 2, the road changes as follows.

3 5 8 4 9

Sangryeol's spells can also reach beyond the ends of the road, and any part of a spell outside the road is ignored. For example, when $K = 3$, a spell can be cast on the 0th, 1st, and 2nd segments. The spell on the 0th segment is ignored, so only the 1st and 2nd segments are affected.

The first line contains $N$, $K$, and the number of candidate segments $Q$. ($1 \le K \le N \le 100{,}000$, $1 \le Q \le 100{,}000$)

The second line contains the sequence $A$ of length $N$ that describes the road. ($-10^9 \le A_i \le 10^9$)

Each of the next $Q$ lines contains a candidate segment. The $i$-th candidate is given by two integers $l_i$ and $r_i$, meaning it covers the segments from the $l_i$-th to the $r_i$-th of the road. ($1 \le l_i \le r_i \le N$)

For each candidate segment, print on its own line the minimum number of spells Sangryeol must cast. If the heights of the road segments cannot be made equal with spells, print $-1$.