SkyCloud

Being stuck in a SkyCloud world is tiresome. Each day consists of the repetitive task of mining clouds, with occasional jump scares from hostile mobs. One day, you find an elytra in a benevolent gift. With this great power, you set your sights on the horizon to reach new clouds.

A server admin tells you there are $N$ clouds in the sky, and that each cloud $i$ is located at a unique altitude of $A_i$. The clouds are conveniently positioned left to right, with the first cloud being the leftmost. With your elytra, you can fly to the nearest cloud that is at most $K$ altitude less than the current cloud you are at (or risk taking significant fall damage). If there are multiple options, choose the cloud with the highest altitude. You cannot fly to clouds higher than your current altitude, as you don’t have rockets.

You imagine $Q$ scenarios. In each scenario $j$, there is a portal at cloud $X_j$ that you wish to reach. The server drops you on a random cloud between $L_j$ and $R_j$. From how many of those clouds can you reach cloud $X_j$?

Input

• The first line contains three space-separated integers, $N$, $K$ and $Q$.
• The second line contains $N$ space-separated integers, $A_1$, $A_2$, … $A_N$.
• The next $Q$ lines each contain three space-separated integers, $X_j$, $L_j$ and $R_j$.

Output

Output $Q$ lines. On each line $j$, output one integer corresponding to the number of clouds between $L_j$ and $R_j$ that can reach cloud $X_j$.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$ for all $1 \leq i \leq N$
• All clouds have a unique altitude.
• $1 \leq X_j, L_j, R_j \leq N$ for all $1 \leq j \leq Q$

Subtasks

• Subtask 1 (10%): $1 \leq N, Q \leq 200$
• Subtask 2 (20%): $1 \leq N, Q \leq 3000$
• Sutbask 3 (20%): $X_j = X_{j+1}$ for all $1 \leq j \leq Q-1$
• Subtask 4 (25%): $L_j = R_j$ for all $1 \leq j \leq Q$
• Subtask 5 (25%): No additional constraints