Note that Subtask 3 is not the same task as Subtasks 1 and 2 although they are very similar.

Subtasks 1 and 2 (99%)

Lester is the principal of the School of Imposture. The school has $N$ students who will be trained to become sussy impostors. When each student enters the school, they are assigned a unique student ID from $1$ to $N$ and are enrolled in Grade $1$. After each year, their grade increases by one. They graduate upon finishing Grade $G$. Their student ID will be taken by a grade $1$ student enters the school in the following year.

Lester is interested in the demographics of his students. You are provided with the current grade of each student with student ID from $1$ to $N$. Lester is now asking you $Q$ questions in the format: How many students with student ID between $A$ and $B$ are currently studying in grade $K$?

Subtask 3 (1%)

Lester will still ask questions of the same format described above. However, instead of asking all $Q$ questions at the same time, Lester only asks one question per year. One year passes after each of Lester's questions, so Grade $1$ students advance to Grade $2$, Grade $2$ students advance to Grade $3$, and Grade $G$ students graduate and are replaced by new Grade $1$ students. You are asked to answer Lester's questions while taking the number of years that passed into consideration.

Input

The first line of input contains four integers $N$, $G$, $Q$ and $S$. $S = 1$ if the input is part of Subtask 3, otherwise $S = 0$.
The second line contains $N$ integers, where the $i$-th integer is the grade of the student with student ID $i$.
Each of the next $Q$ lines contain three integers $A$, $B$ and $K$, the parameters of Lester's question.

Output

For each query, output the answer to Lester's question on a new line.

Constraints

For all subtasks, $1 \le K \le G \le 20; 1 \le A \le B \le N$.
Subtask 1 (30%): $ S = 0; 1 \le N, Q \le 2000$
Subtask 2 (69%): $ S = 0; 1 \le N, Q \le 10^5$
Subtask 3 (1%): $ S = 1; 1 \le N, Q \le 10^5$