IOI 2018 개막식에서 $N$명의 참가자들이 수직선으로 표현되는 직선을 따라 행진합니다. 모든 참가자들은 수직선의 양의 방향으로 향합니다. 시각 $0$에 $i$번째 참가자($1 \le i \le N$, 앞에서부터 셈)는 좌표 $-i$에 서 있습니다. 또한, 기수인 IOI 양은 좌표 $0$에 서 있습니다.

각 참가자는 느림이라고 불리는 값을 가집니다. $i$번째 참가자는 느림 $D_i$를 가집니다. 참가자들은 다음 규칙을 지킵니다:

• 만약 $i$번째 참가자가 자신의 바로 앞에 있는 사람(참가자 또는 IOI 양)으로부터 $D_i+1$ 이상의 거리에 있다면, $i$번째 참가자는 그 사람으로부터 거리가 $1$인 위치로 이동합니다. 그렇지 않다면, $i$번째 참가자는 이동하지 않습니다.

IOI 양은 단위 시간당 수직선 위에서 양의 방향으로 거리 $1$만큼 이동합니다. 참가자는 위에서 설명한 조건이 만족될 때마다 즉시 이동합니다.

당신은 개막식을 취재하는 기자입니다. 사진을 찍어야 했지만, 개막식 내내 깊이 잠들어 버렸습니다. 어쩔 수 없이 당신은 회장의 사진을 찍은 뒤 그 위에 사람들의 그림을 그려 넣어 속이기로 결정했습니다.

속임수가 들통나지 않기 위해, 또는 그림을 그리는 시간을 추정하기 위해, 당신은 다음 $Q$개의 값을 알고 싶습니다:

• 시각 $T_j$에 좌표 $L_j$ 이상 $R_j$ 이하에 서 있는 사람의 수 ($1 \le j \le Q$).

과제

각 참가자의 느림과 $Q$개의 질문에 대한 데이터가 주어졌을 때, 각 질문에 대해 조건을 만족하는 사람의 수를 계산하는 프로그램을 작성하십시오.

입력

표준 입력에서 다음 데이터를 읽으십시오.

• 입력의 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $Q$가 주어집니다. 이는 참가자가 $N$명(IOI 양 제외)이고 질문이 $Q$개 있음을 의미합니다.
• 이어지는 $N$개의 줄 중 $i$번째 줄($1 \le i \le N$)에는 정수 $D_i$가 주어집니다. 이는 앞에서부터 $i$번째 참가자가 느림 $D_i$를 가짐을 의미합니다.
• 이어지는 $Q$개의 줄 중 $j$번째 줄($1 \le j \le Q$)에는 공백으로 구분된 세 정수 $T_j$, $L_j$, $R_j$가 주어집니다. 이 값들은 $j$번째 질문을 나타냅니다.

출력

표준 출력에 $Q$개의 줄을 출력하십시오. 출력의 $j$번째 줄($1 \le j \le Q$)에는 $j$번째 질문에 대한 답을 출력해야 합니다.

제한

모든 입력 데이터는 다음 조건을 만족합니다.

• $1 \le N \le 500\,000$.
• $1 \le Q \le 500\,000$.
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

서브태스크

3개의 서브태스크가 있습니다. 각 서브태스크의 배점 및 추가 제한은 다음과 같습니다:

서브태스크 1 [7점]

• $D_i=1$ ($1 \le i \le N$).

서브태스크 2 [12점]

• $N \le 1\,000$.
• $Q \le 1\,000$.
• $T_j \le 1\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000$ ($1 \le j \le Q$).

서브태스크 3 [81점]

추가적인 제한은 없습니다.

예제

입력 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

출력 1

0
1
1
2
1
2

노트

이 예제 입력에서 참가자들과 IOI 양은 다음과 같이 이동합니다.

아래에서 구간 $[L,R]$은 수직선 위에서 좌표가 $L$ 이상 $R$ 이하인 점들의 집합을 나타냅니다.

• 시각 $0$에 IOI 양은 좌표 $0$에 서 있습니다. 1번째, 2번째, 3번째 참가자는 각각 좌표 $-1$, $-2$, $-3$에 서 있습니다.
• 시각 $1$에 IOI 양은 좌표 $1$로 이동합니다. 아무 참가자도 이동하지 않으며, 1번째, 2번째, 3번째 참가자는 각각 좌표 $-1$, $-2$, $-3$에 서 있습니다. 구간 $[2,4]$에 사람이 없으므로 1번째 질문에 대해 0을 출력합니다.
• 시각 $2$에 IOI 양은 좌표 $2$로 이동합니다. IOI 양과 1번째 참가자 사이의 거리가 이제 $3$이므로, 1번째 참가자는 좌표 $1$로 이동합니다. 1번째, 2번째, 3번째 참가자는 각각 좌표 $1$, $-2$, $-3$에 서 있습니다. 구간 $[2,4]$에는 IOI 양만 있으므로 2번째 질문에 대해 1을 출력합니다.
• 시각 $3$에 IOI 양은 좌표 $3$으로 이동합니다. 아무 참가자도 이동하지 않으며, 1번째, 2번째, 3번째 참가자는 각각 좌표 $1$, $-2$, $-3$에 서 있습니다. 구간 $[2,4]$에는 IOI 양만 있으므로 3번째 질문에 대해 1을 출력합니다.
• 시각 $4$에 IOI 양은 좌표 $4$로 이동합니다. IOI 양과 1번째 참가자 사이의 거리가 이제 $3$이므로, 1번째 참가자는 좌표 $3$으로 이동합니다. 1번째, 2번째, 3번째 참가자는 각각 좌표 $3$, $-2$, $-3$에 서 있습니다. 구간 $[2,4]$에는 IOI 양과 1번째 참가자가 있으므로 4번째 질문에 대해 2를 출력합니다.
• 시각 $5$에 IOI 양은 좌표 $5$로 이동합니다. 아무 참가자도 이동하지 않으며, 1번째, 2번째, 3번째 참가자는 각각 좌표 $3$, $-2$, $-3$에 서 있습니다. 구간 $[2,4]$에는 1번째 참가자만 있으므로 5번째 질문에 대해 1을 출력합니다.
• 시각 $6$에 IOI 양은 좌표 $6$으로 이동합니다. IOI 양과 1번째 참가자 사이의 거리가 이제 $3$이므로, 1번째 참가자는 좌표 $5$로 이동합니다. 그러면 1번째 참가자와 2번째 참가자 사이의 거리가 이제 $7$이므로, 2번째 참가자는 좌표 $4$로 이동합니다. 나아가 2번째 참가자와 3번째 참가자 사이의 거리가 이제 $7$이므로, 3번째 참가자는 좌표 $3$으로 이동합니다. 1번째, 2번째, 3번째 참가자는 각각 좌표 $5$, $4$, $3$에 서 있습니다. 구간 $[2,4]$에는 2번째와 3번째 참가자가 있으므로 6번째 질문에 대해 2를 출력합니다.

입력 2

4 2
1
1
1
1
2 1 4
1 3 6

출력 2

2
0

노트

이 예제 입력은 서브태스크 1의 제한 조건을 만족합니다.

입력 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

출력 3

1
6
0
5
2
7