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

در ابتدا $n$ صف خالی داریم. در هر مرحله،

• یک عدد به انتهای همه‌ی صف‌ها اضافه می‌شود،
• از ابتدای یکی از صف‌ها تعدادی عدد حذف می‌شود و شما باید جمع اعداد حذف شده را چاپ کنید. دقت کنید ممکن است صف به طور کامل خالی شود.

ورودی

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

در $q$ خط بعدی در هر خط،

• $1\ x$

یعنی $x$ به انتهای همه‌ی صف‌ها اضافه می‌شود.

• $2\ i\ j$

از ابتدای صف $i$اُم، $j$ عنصر حذف می‌شود. تضمین می‌شود $j$ حداقل صفر و حداکثر به اندازه‌ی طول فعلی صف است.

$$1 \le n, q \le 300\ 000$$

$$1 \le i \le n$$

$$1 \le x \le 10^9$$

خروجی

به ازای هر اتفاق از نوع دوم عدد خواسته شده را چاپ کنید.

مثال

ورودی نمونه

2 5
1 5
1 17
2 1 1
1 1
2 2 3

خروجی نمونه

5
23

۲ صف داریم و ۵ اتفاق می‌افتد:

1. عدد ۵ به تمامی صف‌ها اضافه می‌شود.
2. عدد ۱۷ به تمامی صف‌ها اضافه می‌شود.
3. از صف اول عنصر ابتدایی (عدد ۵) حذف می‌شود.
4. عدد ۱ به تمامی صف‌ها اضافه می‌شود.
5. از صف دوم ۳ عنصر اول (۵ و ۱۷ و ۱) حذف می‌شود.