• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

مدتی پیش سینا به بیماری سخت «بینتی» دچار شد. او پس از مدت‌ها مبارزه، موفق شد بیماری را شکست داده و سلامتی خود را به دست آورد. پس از این اتفاق او تصمیم گرفت برای کمک به افراد مبتلا به بینتی پیش قدم شده و به جمع آوری کمک های مالی بپردازد.

اما در حین آماده‌سازی متوجه شد بیماری‌های دیگری نیز وجود دارند که فرآیند درمان آن‌ها بسیار هزینه بر است. به همین دلیل او تصمیم به ایجاد \(n\) موسسه‌ی خیریه گرفت که هر کدام برای کمک به افراد مبتلا به یک بیماری خاص فعالیت کنند. علاوه بر این، سینا ساختاری برای این موسسسه‌ها ایجاد کرد تا کمک‌های مالی منحصر به یک بیماری نشوند. در این ساختار برای موسسه‌ی \(i\)ام، محدودیت مالی \(a_i\) تومان در سال در نظر گرفته شده است. به این ترتیب اگر مجموع دریافتی موسسه‌ی \(i\) ام از \(a_i\) فراتر برود، مبلغ اضافه تا پایان سال به صورت خودکار به موسسه‌ی \(i + 1\) ام منتقل می‌شود. در صورتی که دریافتی سال جاری موسسه‌ی \(i + 1\) ام نیز به محدودیت مالی آن رسیده باشد، این روند ادامه پیدا می‌کند و مبلغ اضافه به موسسسه‌ی \(i + 2\) ام منتقل خواهد شد. اگر پس از اتمام محدودیت مالی موسسه‌ی \(n\) ام کمکی به آن برسد، مبلغ دریافت شده به صورت جداگانه برای ایجاد موسسه های جدید ذخیره می‌شود.

متاسفانه با توجه به ساختار نوین این موسسه‌ها ابزار مناسبی برای رسیدگی به امور حساب داری آن وجود ندارد. بنابراین سینا از شما کمک خواسته است که یک برنامه‌ی حساب داری برای موسسه‌هایش پیاده سازی کنید. به طور دقیق‌تر برنامه‌ی شما باید به دو نوع درخواست پاسخ دهد:

• ثبت کمک مردمی به مبلغ \(x\) تومان به موسسه‌ی \(p\)ام.
• اعلام موجودی موسسه‌ی \(k\) ام.

به سینا کمک کنید تا تراکنش‌های مالی موسسه‌هایش را مدیریت کند.

ورودی

در خط اول دو عدد \(n\) و \(q\) با یک فاصله آمده‌اند که به ترتیب تعداد موسسه‌های خیریه و تعداد درخواست‌ها را نشان می‌دهند.

\[1 \leq n, q \leq 2 \times 10^5\]

در خط دوم \(n\) عددهای \(a_1, a_3, \dots, a_n\,\) با فاصله آمده‌اند که محدودیت مالی موسسه‌ها را نشان می‌دهند. در \(i\) امین خط از \(q\) خط بعدی ابتدا یک عدد \(t_i\) آمده است که نوع درخواست را نشان می‌دهد. اگر \(t_i\) یک باشد، پس از آن دو عدد دیگر \(x_i\) و \(p_i\) آمده‌اند که به ترتیب موسسه‌ی هدف و میزان کمک در این تراکنش را نشان می‌دهند. در غیر این صورت \(t_i\) برابر دو است و بعد از آن یک عدد \(k_i\) آمده است که شماره‌ی موسسه‌ی خیریه‌ای است که موجودی آن درخواست شده است.

\[1 \leq p_i, k_i \leq n\] \[1 \leq a_i, x_i \leq 10^9\]

خروجی

در خروجی به ازای هر درخواست از نوع دو یک خط چاپ کنید که موجودی موسسه‌ی درخواست شده در آن آماده است.

مثال

ورودی نمونه ۱

3 6
15 20 18
1 1 22
2 2
1 1 16
1 3 12
2 2
2 3

خروجی نمونه ۱

7
20
ٓ15