+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- چنگیزخان با ارتش عظیمش بار دیگر در فکر حمله به چین است و در پی این تصمیم به سربازانش دستور داده است که $n$ نردبان با $h$ پله پای دیوار بزرگ چین بگذارند. می‌دانیم سربازان چنگیز اگر روی نردبانی باشند هر ثانیه دقیقاً ۱ پله بالا می‌روند. همچنین هر ثانیه یکی از دو اتفاق زیر رخ می‌دهد: - چنگیز به سربازانش دستور می‌دهد که به ازای نردبان‌های $l$ ام تا $r$ ام از هر نردبان دقیقاً $x$ نفر همزمان شروع به بالا رفتن بکنند. - اینکه سربازان چینی از بالای دیوار سنگی بر روی نردبان $i$ ام می‌اندازند که $k$ نفر بالایی نردبان را می‌کشد. دقت کنید که اگر کمتر از $k$ نفر روی نردبان باشند، سنگ تمام افراد روی نردبان را می‌کشد و سپس بدون آسیب دیگری به زمین می‌رسد. این حمله برای $q$ ثانیه اتفاق جدید دارد. بعد از آن هم چنگیز صدایش می‌گیرد و دستور دیگری نمی‌دهد. البته سربازان چینی نیز دیگر سنگی ندارند. سربازان مغولی که روی نردبان‌ها هستند از ترس چنگیز همچنان به بالا رفتن ادامه می‌دهند. برای درک بیشتر سوال به مثال‌ها توجه کنید. در پایان، چنگیز که از حساب و کتاب بدش می‌آید، از شما می‌خواهد به او کمک کنید که بداند چند تن از سربازانش به بالای نردبان‌ها رسیده‌اند. # ورودی در خط اول به ترتیب $n$ و $q$ و $h$ می آیند که نشان دهنده تعداد نردبان‌ها، تعداد اتفاقات و تعداد پله‌های نردبان‌ها هستند. $$1 \leq n, q \leq 200\,000, \quad 1 \leq h \leq 10^9$$ در ادامه $q$ خط داده می شوند که هر یک یکی از دو حالت زیر را دارند که نشان دهنده اتفاق نوع اول و دوم هستند. - $1 \; l\;r\;x$ - $2\;i\;k$ $$1 \leq l \leq r \leq n , \quad 1 \leq x \leq 10^7$$ $$1 \leq i \leq n , \quad 1 \leq k \leq 10^7$$ # خروجی در تنها خط خروجی بگویید که چند سرباز چنگیز بعد از $10^{18}$ ثانیه به بالای نردبان‌ها می‌رسند. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-----:|:-------:|:----------------------------:| | ۱ | ۷ | $1 \leq n, q \leq 2000$ | | ۲ | ۱۲ | $1 \leq h \leq 200$ | | ۳ | ۳۸ | $x,k = 1$ | | ۴ | ۴۳ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 3 3 1 1 1 2 1 2 1 1 2 2 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 5 6 3 2 4 5 1 1 5 2 1 1 3 1 2 4 3 1 1 1 9 2 5 2 ``` ## خروجی نمونه ۲ ``` 20 ```

حل سؤال در بانک سؤالات