운이 없었던 사람

Vini는 아주 열정적인 자동차 도장공이다. 자동차에 페인트칠하는 법을 배운 뒤로 그의 꿈은 국제 자동차 도장 경진대회(ICPC)에 참가하는 것이었다.

매년 Vini가 사는 지역에서는 지역의 모든 경쟁 자동차 도장 팀의 순위를 매기는 지역 대회가 열린다. 상위 x위 안에 든 팀의 도장공들이 ICPC에 나가게 된다. 매년 새로운 참가자가 쏟아지는 아주 흥미진진한 대회지만, 결국 자동차 페인트에서 나오는 독한 연기에 지쳐 모두 은퇴하고 만다.

국가 자동차 도장 예산의 변동과 ICPC의 제약 때문에 이 x값은 해마다 달라질 수 있고, 이 때문에 일부 참가자는 큰 불만을 느끼기도 한다.

Vini가 참가자로서 보낸 마지막 해에 그의 팀은 ICPC 진출까지 한 순위 차이로 밀렸다. 참 운이 없었다! 설상가상으로 그다음 해에는 같은 순위를 기록한 팀이 진출까지 해 버렸다. 이런 억울함 속에서 다른 은퇴 참가자들과 이야기를 나눈 뒤, 그는 많은 사람이 여러모로 비슷한 억울함을 느꼈다는 사실을 알게 되었다.

은퇴한 참가자들은 보통 은퇴한 뒤 몇 년 동안 지역 대회 결과를 지켜본다. 따라서 은퇴하고 한참 뒤에 일어난 x값의 변화 때문에 억울함을 느끼지는 않는다. 더 정확히는, 각 은퇴 참가자는 마지막으로 참가한 해가 ai이고 그때 순위가 pi였으며, 은퇴한 뒤 fi년 동안 결과를 지켜보았다.

마지막 참가에서 ICPC에 진출하지 못한 참가자는, 결과를 지켜본 각 해에 그 해에 참가했다면 진출할 수 있었던 경우 억울함을 느꼈다. 다시 말해, 은퇴한 뒤 fi년까지의 각 해에 대해, 마지막 참가에서 진출하지 못했다면 그 해 ICPC 진출 팀 수가 pi 이상일 때 억울함을 느꼈다.

해마다 진출 팀 수와 은퇴 참가자들의 정보가 주어질 때, 각 은퇴 참가자가 억울함을 느낀 해의 수를 구하자.

첫째 줄에 두 정수 Y와 N이 주어진다 (1 ≤ Y, N ≤ 3 × 105). Y는 대회가 열린 해의 수, N은 Vini가 이야기를 나눈 은퇴 참가자의 수이다. (그렇다, 자동차 도장은 천 년 넘게 이어진 전통이며 아주 인기 있는 일이기도 하다!)

다음 줄에 Y개의 정수 x1, x2, ..., xY가 주어진다 (0 ≤ xi ≤ 105). xi는 각 해에 그 지역에서 ICPC로 나갈 수 있었던 자리 수이다.

다음 N개의 줄에는 각각 세 정수 ai, pi, fi가 주어진다 (1 ≤ ai ≤ Y, 1 ≤ pi ≤ 105, 0 ≤ fi ≤ Y − ai). ai는 i번째 은퇴 참가자가 마지막으로 참가한 해, pi는 i번째 은퇴 참가자 팀의 순위, fi는 i번째 은퇴 참가자가 은퇴한 뒤 결과를 지켜본 햇수이다.

N개의 줄을 출력한다. i번째 줄에는 i번째 은퇴 참가자가 억울함을 느낀 해의 수를 출력한다.