Highway

Time Limit: 10000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3207
64-bit integer IO format: %I64d      Java class name: Main

Description

As we all know, every day, there are hundreds of trucks passing through the highway. As some of the trucks might carry several tons of goods, the highway will be damaged unless it is frequently repaired. The administration of highway is worried about this, so it invented repairing cars to ensure that the cars can pass through the highway.

The highway has an initial durability. If a truck with x tons’ goods pass the highway, its durability will be decreased by x. Once the highway’s durability is less or equal to zero, it will be broken and can never be repaired. The trucks can’t pass through the broken ones.

There are two kinds of repairing cars: T1 can increase the highway’s durability by r, T2 can increase the highway’s durability to p, if the highway’s durability is less than p. Although the repairing cars can pass through the broken parts, the broken parts can’t be repaired.

Input

The input consists of several test cases.

For every test case, there are three integers N (1<=N<=100000), M (1<=M<=100000), I (1<=I<=1000) in the first line, indicating the highway’s length, the numbers of cars and the initial durability of the highway.

Each of the next M lines described the information of cars in the following format:
1 s t d -- There is a truck with d tons’ goods wanted to pass the interval [s, t]. You should check whether the truck can pass it. Notice that if the truck can't pass the whole interval, it will give up the whole passing; otherwise it can pass the highway freely, even if the highway will be broken after the truck’s passing.
2 s t r -- A T1 car will pass the interval [s, t] and increase its durability by r.
3 s t p -- A T2 car will pass the interval [s, t] and increase its durability to p.
You can assume that 1<=s<=t<=N, 1<=d, p, r<=1000

The input ends with N=M=I=0.

Output

For each case, you should return how many trucks can successfully pass the interval.

Sample Input

5 5 5
1 1 3 3
2 2 3 10
1 1 3 3
1 1 3 1
1 2 3 1
5 3 10
1 1 2 5
1 2 3 5
1 1 3 5
0 0 0

Sample Output

3
2

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .