Background

The little square was crushed into dust by the Lord of Darkness.

Is everything really over like this?

Just when everyone thought there was no hope of turning the tables,

parts of the two World Trees that had already been purified began to flicker faintly……

Problem Description

The little square has been revived by the power of the triangle, and it is about to start the final battle with the Lord of Darkness.

The little square’s final goal is to purify the Lord of Darkness.

The Lord of Darkness has a centipede body of length $n$, and at the beginning the brightness level of each segment is $1$.

When the brightness level of a segment reaches a specified value ($k$), we consider this segment to be purified.

To purify the Lord of Darkness, the little square has prepared $m$ types of plans. By their essential differences, these plans can be roughly divided into four types:

1. Change the brightness level of a segment with brightness level $a$ to $b$. (Note that $b$ may be $\le a$.)

2. Change the brightness level of a segment whose brightness level is in the interval from $a1$ to $a2$ to $b1$.

3. Change the brightness level of a segment with brightness level $a1$ to any value in the interval from $b1$ to $b2$.

4. Change the brightness level of a segment whose brightness level is in the interval from $a1$ to $a2$ to any value in the interval from $b1$ to $b2$.

Since using each plan consumes a certain amount of attribute energy, each plan has its own independent upper limit on the number of uses. In one plan, we use $l$ to denote this upper limit.

The little square wants to know the maximum number of segments of the Lord of Darkness’s centipede that can be purified.

Input Format

The first line contains three positive integers $n, m, k$, representing the length of the Lord of Darkness’s centipede body, the total number of plans, and the $k$ described above.

The next $m$ lines each start with two positive integers $op, l$, representing the type of the plan and the upper limit on the number of uses. The input for each plan type is as follows:

If $op = 1$, then two integers $a, b$ follow, with the meaning described above.

If $op = 2$, then three integers $a1, a2, b1$ follow, with the meaning described above.

If $op = 3$, then three integers $a1, b1, b2$ follow, with the meaning described above.

If $op = 4$, then four integers $a1, a2, b1, b2$ follow, with the meaning described above.

The data guarantees that all $1 \le a, b, a1, b1, a2, b2 \le k$.

Output Format

Output one integer in a single line, representing the maximum number of segments that can be purified.

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

4

Hint

First use plans 1, 2, and 3 to change the brightness levels of three segments to $3$, then change them to $2$, and then to $5$.

Then use plan 4 to change the brightness level of one segment to $5$.

For $10\%$ of the testdata, $n = 1, op = 1$.

For another $10\%$ of the testdata, $n = 1, op \le 3$.

For another $10\%$ of the testdata, $n \le 10, op = 1$.

For another $20\%$ of the testdata, $n \le 100, m \le 100, op = 1$.

For $70\%$ of the testdata, $n \le 1000, m \le 1000, op \le 3, k \le 20000$.

For the first $70\%$ of the testdata, the time limit is $500$ ms.

For $100\%$ of the testdata, $n \le 10^7, m \le 20000, 1 \le k \le 10^5, 1 \le l \le 10^5$.

For the last $30\%$ of the testdata, the time limit is $8000$ ms.

The data guarantees that the operations are randomly generated.

Translated by ChatGPT 5