개미와 설탕
시간 제한4초메모리 제한1024 MB
직선 위에 개미와 설탕을 차례로 놓을 때, 각 단계마다 한 개미가 거리 L 안에서 먹을 수 있는 설탕의 최대 개수를 구합니다.
문제
JOI-kun은 생물학자이다. 그는 개미와 설탕을 이용한 실험을 계획한다.
JOI-kun의 실험은 길이가 인 긴 직선 막대 위에서 진행된다. 막대는 왼쪽에서 오른쪽으로 놓여 있다. 가장 왼쪽 끝에서 거리가 인 막대 위의 점을 좌표 의 점이라고 부른다.
아직 막대 위에는 아무것도 없다. JOI-kun은 개의 연산을 수행한다. 번째 연산은 세 정수 , , 로 주어진다.
- 이면, JOI-kun은 좌표 의 점에 개미 마리를 놓는다.
- 이면, JOI-kun은 좌표 의 점에 설탕 조각 개를 놓는다.
개미와 설탕 조각은 매우 작으므로, 같은 점에 여러 개를 놓을 수 있다. JOI-kun은 같은 점에서 여러 연산을 수행할 수도 있다.
이 실험의 개미에게는 특이한 성질이 있다. JOI-kun이 손뼉을 치면, 모든 개미가 다음을 수행한다.
- 개미로부터 거리가 이하인 곳에 설탕 조각이 하나라도 있으면, 개미는 그중 하나를 골라 먹는다.
여러 개미가 같은 시간에 같은 설탕 조각을 먹을 수도 있다.
모든 ()에 대해, JOI-kun은 다음 질문의 답을 알고 싶어 한다. JOI-kun이 번째 연산 후에 손뼉을 친다고 하자. 적어도 한 마리의 개미가 먹는 설탕 조각의 최대 개수는 얼마인가?
연산들과 의 값이 주어졌을 때, 모든 에 대해 이 질문에 답하는 프로그램을 작성하라.
JOI-kun은 실제로 손뼉을 치지 않는다. 그러므로 개미의 위치는 변하지 않고, 설탕 조각도 먹히지 않는다.
입력
표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.
Q L
T_1 X_1 A_1
T_2 X_2 A_2
...
T_Q X_Q A_Q
출력
줄을 표준 출력에 쓴다. 번째 줄에는 번째 연산 후에 JOI-kun이 손뼉을 쳤을 때, 적어도 한 마리의 개미가 먹는 설탕 조각의 최대 개수를 출력한다.
제한
- .
- ().
- 는 또는 이다 ().
- () ().
- () ().