There is garden which contains N water fountains, each placed at distance 1 to N Each water fountain Every morning Q people come to Walk in garden. People are represented as follow L R K : Each people drink water from fountain numbered L to R and reduce their water level to max (0,A[i]-K) Assuming people come in serial order, find the count of fountains with zero total water level after each person.

Problem Constraints 1 <= N, Q <= 10 ^ 5 1 <= A[i], K <= 10 ^ 9 1<=L<=R<=N

First argument of input contains integer array A of size N. Second argument of input contains Qx3 integer matrix denoting people.

Example Input

Input A=[5,7,3] B=[[1, 2, 1],[2, 3, 1],[1,3,4]]

Input 2: A=[1] B=[1, 1, 10]

Output 1 [0,0,2]

output 2 [1]