- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...
برای حل این بحران، مسریکس ماشین زمان میسیکس را قرض می‌گیرد و به عصر دایناسورها سفر می‌کند. او می‌داند که در آن زمان، نژادهای مختلفی از هر دایناسور وجود داشته است و خصوصیت مشترک دایناسورهای از هر نژاد، تعداد پاهای آن‌هاست! یعنی ممکن نیست دو دایناسور هم‌نژاد وجود داشته باشند که تعداد پاهایشان فرق داشته باشد.
از آن جایی که اگر مسریکس حواسش نباشد ممکن است زیر پای کُرّه دایناسورها له شود، کنار یک بزرگ‌راه پنهان شده و به دایناسورهایی که از پل عابر پیاده‌ی بالای بزرگ‌راه رد می‌شوند نگاه می‌کند. البته چون یک بیلبورد تبلیغاتی جلوی پل عابر نصب شده است، مسریکس فقط می‌تواند از زیر بیلبورد، پاهای دایناسورها را ببیند. جالب است بدانید او می‌تواند از شکل پاهای دایناسورها، نژاد آن‌ها را بفهمد.
مسریکس هر دسته پای متوالی که متعلّق به یک نژاد از دایناسورها باشد را ببیند، به شما تعداد و نژاد آن دسته پا را می‌گوید. اگر برای مدّت زیادی هیچ پایی از روی پل عابر عبور نکند، مسریکس به این نتیجه می‌رسد که هر دایناسور یا به طور کامل از روی پل رد شده است و یا هنوز هیچ کدام از پاهایش را روی پل نگذاشته است. در این حالت برای این که سکوت را بشکند از شما می‌پرسد که «تعداد پاهای نژادهای مختلف دایناسورها چند حالت می‌تونه داشته باشههه؟»
مثلا اگر مسریکس بگوید که «۱ پا متعلّق به نژاد ۱ روی پل عابر دیدم، بعد ۴ پا متعلّق به نژاد ۲ روی پل عابر دیدم و بعد ۱ پا متعلّق به نژاد ۱ دیدم و برای مدّت زمان طولانی دیگه پایی از روی پل عابر رد نشد، بگو تعداد حالات پاهای دایناسورها چند تاست.» شما باید به او بگویید ۶. چرا که ممکن است دایناسورهایی که از نژاد ۱ هستند ۱ یا ۲ پا داشته باشند و دایناسورهایی که از نژاد ۲ هستند می‌توانند ۱، ۲ یا ۴ پا داشته باشند. و اگر بعد از آن به شما بگوید که «۳ پا متعلّق به دایناسور نژاد ۲ دیدم و برای مدّت طولانی کسی از روی پل رد نشد، دوباره بگو چند حالت دارههه.» شما باید بگویید ۲! چرا که دایناسورهای نژاد ۲ فقط ۱ پا می‌توانند داشته باشند.
هم‌چنین مسریکس فرض می‌کند نژادهایی که تا به حال هیچ پایی از آن نوع از پل رد نشده است منقرض شده‌اند و شما نباید در شمارش تعداد حالات، به تعداد پاهای نژادهای مشاهده نشده اهمّیت بدهید. برای مثال اگر مسریکس پیش از آن که دایناسوری از پل عبور کند از شما تعداد حالات را بپرسد، شما باید در جواب عدد ۱ را بگویید.
حواستان باشد که هنگامی که مسریکس دو مرتبه پاهای یک نژاد را می‌بیند، اگر بین این دو مرتبه هیچ پرسشی نکرده باشد، ممکن است همه پاهایی که در این دو مرتبه دیده متعلّق به یک دایناسور باشد اما اگر بین آن‌ها پرسشی انجام داده باشد، قطعا پاهای دایناسورهای مختلف بوده‌اند.
مشاهدات مسریکس در ورودی آمده است. به ازای هر پرسش مسریکس، جواب آن پرسش را در خروجی چاپ کنید تا او بتواند جلوی گرمایش را بگیرد. فقط چون این مقدار ممکن است خیلی بزرگ باشد، شما باید باقی مانده‌ی آن به $1000000007 (10^9 + 7)$ را چاپ کنید.
ورودی
در سطر اوّل ورودی عدد $q$، تعداد صحبت‌های که مسریکس با شما می‌کند، آمده است.
هر یک از $q$ سطر بعد صحبت‌های مسریکس را به ترتیب زمان گفته شدنشان مشخّص می‌کنند. هر سطر ۲ حالت دارد!
+ c t
یعنی «دیدم که $c$ پا متعلّق به دایناسور نژاد $t$ از روی پل رد شد.»
?
یعنی «خیلی وقته کسی رد نشده. بگو تعداد پاهای این دایناسورها چند حالت داره؟»
$$1 \leq q \leq 100\ 000$$ $$1 \leq c \leq 1\ 000\ 000$$ $$1 \leq t \leq 100\ 000$$
تضمین می‌شود مجموع تعداد پاهایی که از هر نژاد دایناسور مشاهده می‌شوند از $1\ 000\ 000$ بیشتر نخواهد شد.
خروجی
تعداد سطرهای خروجی به تعداد صحبت‌های نوع دوم(?) است و در $i$-امین سطر باید پاسخ $i$-امین پرسش را چاپ کنید.
مثال
ورودی نمونه ۱
5
+ 30 1
+ 10 2
?
+ 2 2
?
خروجی نمونه ۱
32
16
ارسال پاسخ برای این سؤال