정원사

온조는 정원 $N$개를 가꾸는 정원사이다. 처음에는 어느 정원에도 식물이 심어져 있지 않고, 정원 하나에 심을 수 있는 식물의 수에는 제한이 없다. 모든 식물은 하루에 $k$만큼 자란다. 즉, 높이가 $h$인 식물을 $x$번째 날에 심었다면 $y$번째 날의 높이는 $h + k(y - x)$이다. 온조는 작업 $M$개를 수행해 정원 $N$개를 가꾸려고 한다.

작업은 세 종류이다.

• 1 t x h: $t$번째 날에 $x$번째 정원에 높이가 $h$인 식물을 하나 심는다.
• 2 t l r h: $t$번째 날에 $l$번째 정원부터 $r$번째 정원까지 심어져 있는 식물 중에서 높이가 $h$를 넘는 것을 모두 뽑아낸다. 높이가 $h$와 같은 식물은 그대로 둔다.
• 3 t l r: $t$번째 날에 $l$번째 정원부터 $r$번째 정원까지 심어져 있는 식물의 수를 출력한다.

온조는 솜씨 좋은 정원사라서 첫 번째 작업과 두 번째 작업은 쉽게 해내지만, 수학에 약해 세 번째 작업은 버거워한다. 세 번째 작업의 답을 대신 구해 주자.

첫째 줄에 정원의 수 $N$ ($1 \le N \le 10^5$), 온조와 당신이 수행할 작업의 수 $M$ ($1 \le M \le 10^6$), 모든 식물이 하루에 자라는 높이 $k$ ($1 \le k \le 10^9$)가 주어진다.

둘째 줄부터 $M$개의 줄에 작업의 정보가 날짜가 증가하는 순서로 주어진다. $l$, $r$, $x$는 $1$ 이상 $N$ 이하이고 $l \le r$이며, 나머지 수는 모두 $1$ 이상 $10^9$ 이하의 자연수이다. 온조는 같은 날에 작업을 두 개 하는 것을 원하지 않으므로, 하루에 수행하는 작업은 최대 하나이다.

세 번째 작업의 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다. 작업 $M$개 중에 세 번째 작업이 적어도 하나 있다.