마이크로스파이크

가정용 전력 사용을 연구하기 위해 연구진은 주택용 전력 소비 시뮬레이터를 만들었다. 이 소프트웨어는 각 주택에서 여러 가전제품의 전력 소비를 시뮬레이션한다. 목표는 전력 사용의 마이크로스파이크, 즉 전체 전력 소비가 지정된 한계를 넘어서는 짧은 구간을 찾아내는 것이다.

시뮬레이션이 시작되기 전에는 모든 가전제품이 꺼져 있다(전력을 소비하지 않음). 시뮬레이션 도중 여러 시점에 가전제품이 전력 소비를 늘리거나 줄인다. 그럴 때마다 시뮬레이터는 가전제품 번호, 그 가전제품의 직전 변화 이후(첫 변화라면 시뮬레이션 시작 이후) 경과한 시간(초), 그리고 전력 변화량(와트)을 담은 기록을 출력한다.

하나의 가전제품에 대한 기록들은 시간 순서대로 나온다. 그러나 서로 다른 가전제품의 기록은 임의의 순서로 섞여 있어서, 가전제품 $A$의 기록이 가전제품 $B$의 기록보다 먼저 나왔다고 해서 $A$의 사건이 $B$의 사건보다 먼저 일어났다고 볼 수는 없다.

전력 한계 $M$과 시간 한계 $S$가 주어질 때, 마이크로스파이크란 전체 전력 $P$가 계속 $M$을 초과하는($P > M$) 극대 구간 중에서, 그 지속 시간 $D$(초)가 $1 \le D \le S$를 만족하는 것을 말한다. 마이크로스파이크는 시작(전체 전력이 $M$을 초과하게 되는 순간)과 끝(전체 전력이 다시 $M$ 이하로 내려가는 순간)이 모두 기록되어 있을 때에만 센다. 시뮬레이션이 끝나는 시점에 한계를 넘고 있는 가전제품은 꺼지지 않으므로, 다시 $M$ 이하로 내려오지 않는 구간은 세지 않는다.

하나 이상의 시뮬레이션에 대한 기록을 읽어, 각 시뮬레이션에서 마이크로스파이크가 몇 번 발생하는지 세어라.

입력은 하나 이상의 시뮬레이션을 담는다. 각 시뮬레이션은 공백 하나로 구분된 세 정수 $T$, $M$, $S$가 있는 줄로 시작한다. 여기서 $T$는 총 시뮬레이션 시간(초, $0 \le T \le 100000$), $M$은 전력 한계($0 \le M \le 10^9$), $S$는 시간 한계($1 \le S \le 1000$)이다.

머리글 줄 다음에는 최대 $N$개의 전력 변화 줄이 이어진다($0 \le N \le 1000000$). 각 줄에는 공백 하나로 구분된 세 정수 $a$, $t$, $p$가 있다. $a$는 가전제품 번호($1 \le a \le 100000$), $t$는 그 가전제품의 직전 변화 이후 경과 시간(초, $0 \le t \le T$), $p$는 전력 변화량(와트, $-10000 \le p \le 10000$)이다. 0 0 0 줄은 현재 시뮬레이션의 전력 변화 줄이 끝났음을 나타낸다.

머리글 줄이 0 0 0이면 전체 입력이 끝난다. 개별 가전제품의 전력 값은 절대 음수가 되지 않으며, 전체 전력 소비는 $1000000000$을 넘지 않는다고 가정해도 된다. 모든 전력 변화는 해당 초가 시작되는 순간에 즉시 적용된다.

각 시뮬레이션마다 관측된 마이크로스파이크의 개수를 한 줄에 하나씩 출력한다.

예제 입력에 대한 전체 전력 소비 그래프다. 가로축의 눈금은 각 초가 시작되는 지점을 나타낸다. 모든 전력 변화는 해당 초가 시작되는 순간에 즉시 적용된다. 시각 $10$에 그려진 막대는 시뮬레이션의 일부가 아니며, 시뮬레이션이 끝난 뒤에도 계속 유지되는 전력 수준을 보여주기 위해 그려 넣은 것이다.