Discribition

有一个长度为n的序列，每次询问l~r的区间内有多少个小于等于s的数。

Format

Input

第1行包括三个整数n，m，A。表示序列长度，询问个数和模数。
第2行共有n个整数，第i个数表示这个序列的第i-1位。
第3~m+2行，每行包括一个三个数l，r，k，代表一个询问。
这个询问的s=(k+ans)%A;
其中ans为上一次询问的答案，一开始ans=0。

Output

对于每次询问，输出l~r的区间内有多少个小于等于s的数。

Example

Input

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

Output

4
1
1
5
2
3
1
2
5
3

Data range

对于100%的数据:1<=n<=500000,1<=m<=200000,0<=ai<=1e9,1<=A<=1e9