시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB998100.000%

문제

Vini é um pintor de carros muito dedicado. Desde que ele aprendeu como pintar carros, o seu sonho tem sido participar da Internacional Competição de Pintores de Carros (ICPC).

Todo ano a região de Vini tem uma competição local para classificar todos os times competitivos de pintores de carro da região. Pintores em times que se classificaram nas melhores x posições avançam para competir na ICPC. E uma competição muito emocionante com muitos competidores novos em ´ todos os anos, até que a fumaça nociva das tintas eventualmente faz com que os competidores se aposentem permanentemente.

Por causa de variações de verba e também por restrições da ICPC, a quantidade x pode variar de ano pra ano, o que pode acabar causando desgosto de alguns dos competidores.

No último ano de Vini como competidor, o seu time estava a uma posição de se qualificar para a ICPC. Que azar! Para fazer com que o seu sentimento de “má sorte” ficasse ainda mais forte, no ano seguinte o time que obteve a mesma colocação se classificou para a ICPC! Apesar do sentimento, depois de falar com outros antigos competidores, ele notou que muitos deles já haviam se sentido azarados de uma forma ou de outra.

Antigos competidores geralmente seguem os resultados das competições regionais por alguns anos após se aposentarem. Portanto, um competidor não se sentiria azarado pelas mudanças em x que acontecessem muitos anos após se aposentar. Mais precisamente, cada antigo competidor participou da sua última competição no ano ai, se posicionando na posição pi e, após se aposentar, seguiu os resultados pelos fi anos seguintes.

Um competidor que não se qualificou para a ICPC em sua última participação se sentiu azarado em todos os anos em que ele seguiu os resultados e nos quais ele teria se classificado se tivesse competido. Em outras palavras, para cada ano até fi anos após se aposentar, se ele não se qualificou em sua última participação, ele se sentiu azarado se o número de times qualificados para a ICPC naquele ano foi ao menos pi.

Dado o número de vagas por ano, e as informações sobre cada antigo competidor, nós gostaríamos de saber em quantos anos cada antigo competidor se sentiu azarado.

입력

A primeira linha contém dois inteiros Y e N (1 ≤ Y, N ≤ 3 × 105), representando a quantidade de anos de competições e a quantidade de antigos competidores com quem Vini conversou, respectivamente. (Sim, pintar carros é uma tradição milenar, e bem popular!).

A próxima linha contém Y inteiros x1, x2, . . . , xY (0 ≤ xi ≤ 105), representando quantas vagas para a ICPC a região teve em cada ano.

Cada uma das seguintes N linhas contém três inteiros ai, pi e fi (1 ≤ ai ≤ Y , 1 ≤ pi ≤ 105, 0 ≤ fi ≤ Y −ai), representando o ano em que o i-ésimo antigo competidor teve sua última participação, a colocação do time do i-ésimo antigo competidor naquele ano, e por quantos anos o i-ésimo antigo competidor seguiu os resultados após se aposentar, respectivamente.

출력

Imprima N linhas, onde a i-ésima linha deve conter um inteiro representando quantos anos o i-ésimo antigo competidor se sentiu azarado.

예제 입력 1

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

예제 출력 1

3
0
1

예제 입력 2

4 1
8 8 8 8
1 7 3

예제 출력 2

0