محاصره (Siege)

چنگیزخان با ارتش عظیمش بار دیگر در فکر حمله به چین است و در پی این تصمیم به سربازانش دستور داده است که $n$ نردبان با $h$ پله پای دیوار بزرگ چین بگذارند. می‌دانیم سربازان چنگیز اگر روی نردبانی باشند هر ثانیه دقیقا ۱ پله بالا می‌روند. همچنین هر ثانیه یکی از دو اتفاق زیر رخ می‌دهد:

• چنگیز به سربازانش دستور می‌دهد که به ازای نردبان‌های $l$ام تا $r$ام از هر نردبان دقیقا $x$ نفر همزمان شروع به بالا رفتن بکنند.
• اینکه سربازان چینی از بالای دیوار سنگی بر روی نردبان $i$ام می اندازند که $k$ نفر بالایی نردبان را می‌کشد. دقت کنید که اگر کمتر از $k$ نفر روی نردبان باشند، سنگ تمام افراد روی نردبان را می‌کشد و سپس بدون آسیب دیگری به زمین می‌رسد.

این حمله برای $q$ ثانیه اتفاق جدید دارد. بعد از آن هم چنگیز صدایش می‌گیرد و دستور دیگری نمی‌دهد. البته سربازان چینی نیز دیگر سنگی ندارند. سربازان مغولی که روی نردبان‌ها هستند از ترس چنگیز همچنان به بالا رفتن ادامه می‌دهند. برای درک بیشتر سوال به مثال‌ها توجه کنید.

در پایان، چنگیز که از حساب و کتاب بدش می‌آید، از شما میخواهد به او کمک کنید که بداند چند تن از سربازانش به بالای نردبان‌ها رسیده‌اند.

در خط اول به ترتیب $n$ و $q$ و $h$ می‌آیند که نشان‌دهنده تعداد نردبان‌ها، تعداد اتفاقات و تعداد پله‌های نردبان‌ها هستند.

در ادامه $q$ خط داده می شوند که هر یک یکی از دو حالت زیر را دارند.

• $\texttt{1} \quad l \quad r \quad x$: که نشان‌دهنده اتفاق نوع اول است و یا
• $\texttt{2} \quad i \quad k$: که نشان‌دهنده اتفاق نوع دوم است.

در تنها خط خروجی بگویید که چند سرباز چنگیز بعد از $10^{18}$ ثانیه به بالای نردبان‌ها می‌رسند.

• زیرمسئله اول (۷ نمره): $1 \leq n, q \leq 2000$
• زیرمسئله دوم (۱۲ نمره): $1 \leq h \leq 200$
• زیرمسئله سوم (۳۸ نمره): $x, k = 1$
• زیرمسئله چهارم (۴۳ نمره): بدون محدودیت اضافی

• $1 \leq n\, , \, q \leq 200000$
• $1 \leq h \leq 10^9$
• $1 \leq l \leq r \leq n$
• $1 \leq i \leq n$
• $1 \leq k\, , \, x \leq 10^7$

در ورودی نمونه اول؛

• در ثانیه‌ی اول دو سرباز یکی از نردبان اول و دیگری از نردبان دوم شروع به بالا رفتن می‌کنند.
• در ثانیه‌ی دوم یک سنگ روی نردبان اول انداخته می‌شود که یک سرباز را می‌کشد.
• در ثانیه سوم یک سنگ روی نردبان دوم انداخته می‌شود که کسی را نمی‌کشد زیرا سربازی که روی نردبان دوم بوده، قبلاً به بالای دیوار چین رسیده‌است.

• سوال قبل