Gardener

Onjo is a gardener who tends $N$ gardens. No garden holds any plant at the start, and there is no limit on how many plants one garden can hold. Every plant grows by $k$ per day. If a plant of height $h$ is planted on day $x$, its height on day $y$ is $h + k(y - x)$. Onjo performs $M$ operations on the $N$ gardens.

There are three kinds of operations.

• 1 t x h: on day $t$, plant one plant of height $h$ in garden $x$.
• 2 t l r h: on day $t$, pull out every plant in gardens $l$ through $r$ whose height is greater than $h$. A plant whose height equals $h$ stays.
• 3 t l r: on day $t$, print the number of plants in gardens $l$ through $r$.

Onjo handles the first and the second operation easily, but the third one is hard for him because he is weak at arithmetic. Answer the third operation for him.

The first line contains the number of gardens $N$ ($1 \le N \le 10^5$), the number of operations $M$ ($1 \le M \le 10^6$), and the daily growth $k$ of every plant ($1 \le k \le 10^9$).

Each of the next $M$ lines describes one operation, given in increasing order of day. $l$, $r$, and $x$ are between $1$ and $N$ with $l \le r$, and every other number is an integer between $1$ and $10^9$. Onjo refuses to do two operations on the same day, so at most one operation happens per day.

Print the answer to each third operation on its own line, in the order the operations are given. At least one of the $M$ operations is a third operation.