Description

There is a beautiful fairy tale: at the end of the sky lies a “Candy Kingdom,” where everything from skyscrapers to tiny flowers and grass is made of candy. Even more magical, the sky is filled with colorful candy clouds, and soon a dense candy rain falls from above: red for strawberry candy, yellow for lemon candy, green for mint candy, black for chocolate candy… At these times, the children of the Candy Kingdom take out bags of all sizes to catch the candies falling from the sky and bring them back to share with their friends.

Z, who loves candies, dreams of visiting such a fairy-tale land. As the saying goes, what you think about during the day comes to you in your dreams at night. One night, Z dreamed that he arrived at the “Candy Kingdom.” To his surprise, at any moment, all clouds in the sky have distinct colors, and each cloud keeps dropping candies of its own color. Even more interestingly, all clouds are moving back and forth at a uniform speed. Imagine the sky has boundaries, and all clouds perform back-and-forth motion exactly between the two boundaries. In each unit of time, a cloud moves one unit to the left or right. When the left edge of a cloud touches the left boundary of the sky, it reverses direction and moves right; when the cloud has completely moved out beyond the right boundary of the sky, it reverses direction and moves left.

We can imagine the sky as a 2D Cartesian plane, and each cloud as a line segment (possibly degenerated to a point):

As shown above, let the left boundary of the sky be 0 and the right boundary be $len$. There are 5 clouds in total. The cloud labeled 1 is just reversing to move right, and the cloud labeled 2 is just reversing to move left.

Ignore the vertical coordinates of clouds; they do not affect each other during motion.

Z notices that clouds may appear in the sky over time (starting at some initial position and moving in some direction), and some clouds may disappear after some time, while candies keep falling during their motion. Z decides to use many bags to catch candies. Each bag has infinite capacity but a finite opening width. For example, at time $T$, if Z uses a bag covering the $x$-coordinate interval $[L, R]$ to catch candies, and if there exists a position $x \in [L, R]$ where candies of some color are falling at that instant, then the bag is considered to be able to catch candies of that color. In extreme cases, the interval of the bag opening may degenerate to a point, such as $[0, 0]$ or $[1, 1]$, but it can still catch candies at the corresponding position. Since the total number of candies that can be caught is usually very large, Z wants to know, at each moment he takes out a bag (i.e., at the instant of querying), how many distinct colors of candies his bag can catch.

The falling time of candies is negligible.

Input Format

The first line contains two positive integers $n$, $len$, denoting the total number of events and the sky’s “boundary.”

Then there are $n$ lines, each describing an event. All events occur in the order given. The first number $k$ on each line ($k \in \{1, 2, 3\}$) denotes the event type: insertion, query, or deletion. The formats are as follows:

$T_i$ are in non-decreasing order.

Output Format

For each query event, output exactly one line containing the answer to that query, i.e., the number of distinct colors of candies the bag can catch.

10 10 
1 0 10 1 3 -1 
2 1 0 0 
2 11 0 10 
2 11 0 9 
1 11 13 4 7 1 
2 13 9 9 
2 13 10 10 
3 100 13 
3 1999999999 10 
1 2000000000 10 0 1 1

1 
1 
0 
2 
1 

Hint

[Sample Explanation]

There are 10 events in total: 3 insertions, 5 queries, and 2 deletions.

At time 0, a cloud of color 10 appears with initial position $[1, 3]$ and direction left.

At time 1, a bag with range $[0, 0]$ can catch color 10 (the cloud is at $[0, 2]$).

At time 11, a bag with range $[0, 10]$ can catch color 10 (the cloud is at $[10, 12]$). At time 11, a bag with range $[0, 9]$ cannot catch color 10 (the cloud is at $[10, 12]$). At time 11, a cloud of color 13 appears with initial position $[4, 7]$ and direction right.

At time 13, a bag with range $[9, 9]$ can catch two different colors: 10 (the cloud is at $[8, 10]$) and 13 (the cloud is at $[6, 9]$).

At time 13, a bag with range $[10, 10]$ can catch only color 10 (the cloud is at $[8, 10]$), and cannot catch color 13 (the cloud is at $[6, 9]$).

At time 100, the cloud of color 13 disappears.

At time 1999999999, the cloud of color 10 disappears.

At time 2000000000, another cloud of color 10 appears with initial position $[0, 1]$ and direction right.

Constraints

For all data, $0 \le T_i \le 2000000000$, $1 \le C_i \le 1000000$. The sequence $\{T_i\}$ is non-decreasing, i.e., $T_1 \le T_2 \le \dots \le T_{n-1} \le T_n$.

For all insertion events, let $P_i = R_i - L_i$, i.e., $P_i$ denotes the length of each cloud.

Translated by ChatGPT 5