+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۱۰۲۸ ایا**، **دوره ۲۸ ایا** را بسیار خفن می‌پنداشتند(زیرا **دوره ۲۸ ایا** واقعا خفن بودند). اعتقاد **دوره ۱۰۲۸ ایا** به خفونت **دوره ۲۸ ایا** چنان بود که فکر می‌کردند **دوره ۲۸ ایا** می‌توانستند حتی مساله توقف را حل کنند! مساله توقف ( به انگلیسی : Halting problem ) مطرح می کند که آیا می توان برنامه ای نوشت که یک برنامه از ورودی بگیرد و تعیین کند که آیا برنامه متوقف می شود یا خیر. ثابت شده که در حالت کلی، الگوریتمی برای حل این مساله وجود ندارد. مسئول **دوره ۱۰۲۸ ایا** برای اینکه اعتماد به نفس **دوره ۱۰۲۸ ایا** تقویت شود، نسخه ساده شده‌ای از مساله هالت را به آنها داد تا آنها فکر کنند مثل **دوره ۲۸ ایا** خفن هستند. در این نسخه‌ ساده شده سه نوع دستور موجود است: ``` assign a = b + c cout a goto l ``` که در آن $a$ و $b$ و $c$ یک **حرف کوچک انگلیسی** (که نام یک متغیر است) یا یک **عدد یک رقمی** هستند و $l$ شماره خطی از برنامه است. تضمین می‌شود که بعد از `assign` متغیر `a` همیشه یک حرف کوچک انگلیسی است. شما باید خط به خط برنامه را دنبال کنید، در صورتی که برنامه پایان‌ناپذیر است، $-1$ را چاپ کنید. در غیر این‌صورت خروجی این برنامه را چاپ کنید. در این برنامه `cout` به معنای چاپ کردن یک عدد یا یک متغیر است. `goto` به معنای پرش به یک خط خاص است (خط‌ها از ۱ شماره‌گذاری شده‌اند). `assign a = b + c` یعنی $b+c$ را در متغیر $a$ قرار بده. هر حرف کوچک انگلیسی نشان‌دهنده یک متغیر است و محتوای همه‌ متغیرها در ابتدا صفر می‌باشد. با توجه به اینکه جواب مسئله ممکن است بزرگ شود شما باید **باقی مانده خروجی بر $10^9+7$** را بگویید. # ورودی در ورودی یک برنامه به شما داده می‌شود. در خط اول $n$ تعداد خط‌های برنامه و در $n$ خط بعد در هر خط یک دستور از برنامه داده می‌شود. $$1 \le l \le n \le 100\ 000$$ # خروجی اگر برنامه داده‌شده تمام نمی‌شود، در تنها سطر خروجی $-1$ چاپ کنید. در غیر اینصورت خروجی‌های برنامه‌ (به ازای هر `cout`) را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 assign a = 2 + 2 cout a ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 4 assign a = 1 + 0 cout a assign a = a + a goto 2 ``` ## خروجی نمونه ۲ ``` -1 ``` ## ورودی نمونه ۳ ``` 7 cout 0 goto 5 cout 1 goto 7 cout 2 goto 3 cout 3 ``` ## خروجی نمونه ۳ ``` 0 2 1 3 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۲۸ ایا** بعضی وقت‌ها خسته می‌شدند. **دوره ۱۰۲۸ ایا** بعد از فهمیدن این موضوع می‌خواهند آن برای تخریب وجهه **دوره ۲۸ ایا** استفاده کنند. **دوره ۲۸ ایا** در زمان خستگی همه دور هم جمع می‌شدند و فعالیت روزانه استاد بزرگ را تماشا می‌کردند. استاد بزرگ هر روز یک تکه چوب دارای $n$ مربع به هم چسبیده تهیه می‌کرد و در خانه $i$ ام آن عدد $a_i$ را می‌نوشت. پس از تهیه چوب استاد عملیات زیر را روی تمام مرز‌‌های مربع‌های متوالی انجام می‌داد ($n-1$ مرز داریم). استاد با ذکر غوودا ضربه‌‌ای محکم به مرز می‌زد که این ضربه به احتمال $\frac{1}{2}$ چوب را می‌شکاند و به احتمال $\frac{1}{2}$ نمی‌شکاند (‌استاد در دوران پیری به سر می‌برد به همین دلیل بعضی وقت‌ها چوب نمی‌شکست). آنگاه **دوره ۲۸ ایا** مات و مبهوت از مهارت استاد و به نشانه احترام جمع اعداد روی هر تکه چوب باقی‌مانده را بر سردر شاز نصب می‌کردند (برای مثال اگر $n = 3$ و اعداد روی تکه‌ها به ترتیب $17\ , 2\ , 3\ $ بودند و ضربه‌ی استاد مرز بین اولین تکه و دومین تکه را نمی‌شکاند ولی مرز بین دومین تکه و سومین را می‌شکاند، **دوره ۲۸ ایا** اعداد $5\ ,17\ $ را بر سر در شاز نصب می‌کردند). **دوره ۱۰۲۸ ایا** برای اثبات خفونت خود می‌خواهند امیدریاضی تعداد اعداد متفاوتی که سر در شاز نصب می‌شود را بیابند (برای مثال تعداد اعضای متفاوت مجموعه‌ی $\{7, 1, 2, 7, 3, 5, 1, 1\}$ برابر $5$ است). ثابت می‌شود که جواب مورد نظر را می توان به صورت کسر $\frac{P}{Q}$ نشان داد (که قابل ساده کردن نیست). از شما خواسته شده که $P.Q^{-1}$ را در پیمانه‌ $10^9+7$ خروجی دهید. # ورودی در خط اول ورودی عدد $n$ داده می‌شود. سپس در خط بعدی $n$ عدد طبیعی می‌آیند که $i$ امین آنها $a_i$ می‌باشد. $$1 \le n \le 500 $$ $$-10^{15} \le a_i \le 10^{15}$$ # خروجی امیدریاضی تعداد اعداد متفاوت نصب شده در سردر را به فرم $P.Q^{-1}$ در پیمانه $10^9+7$ خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 2 -77 14 ``` ## خروجی نمونه ۱ ``` 500000005 ``` به احتمال $\frac{1}{2}$ مجموعه ، $\{-63\}$ به احتمال $\frac{1}{2}$ مجموعه ، $\{-77,14\}$ بر سردر شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2}{2}$ می‌باشد. ## ورودی نمونه ۲ ``` 3 1 2 3 ``` ## خروجی نمونه ۲ ``` 750000007 ``` به احتمال $\frac{1}{4}$ مجموعه ، $\{6\}$ به احتمال $\frac{1}{4}$ مجموعه ، $\{1,5\}$ به احتمال $\frac{1}{4}$ مجموعه ، $\{3,3\}$ به احتمال $\frac{1}{4}$ مجموعه ، $\{1,2,3\}$ بر سر در شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2+1+3}{4}$ می‌باشد.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در زمان **دوره ۱۰۲۸ ایا** ربات‌ها آنقدر پیشرفت کرد‌ه بودند که بتوانند کنترل جهان را بدست بگیرند! (همانطور که پیشگوی بزرگ **دوره ۲۸ ایا** پیش‌بینی کرده بود). برای مقابله با این تهدید بزرگ تیم زبده‌ای از **دوره ۱۰۲۸ ایا** دست‌‌بکار شدند. طبق آخرین اخبار رسیده از جاسوس‌هایمان، ربات‌ها توانایی تولید ربات‌های دیگر را پیدا کرده‌اند. اما از آنجایی که اینکار برایشان سخت است، یک ربات به تنهایی نمی‌تواند یک ربات دیگر بسازد و هر ربات جدید را دقیقا دو ربات با همکاری یکدیگر می‌سازند. همچنین می‌دانیم که یک ربات جدید، دو ربات تولید‌کننده‌اش را پدر خود می‌داند. **دوره ۱۰۲۸ ایا** به‌تازگی حمله موفقیت‌آمیزی به مقرر ربات‌ها داشته‌اند و طی این عملیات دو تا از ربات‌ها به نام $a$ و $b$ را گروگان گرفته‌اند و حالا می‌خواهند از ربات $a$ بازجویی کنند! از آنجایی که ربات $a$ دهنش قرص قرص است، **دوره ۱۰۲۸ ایا** تصمیم گرفتند به روش‌های سخت تر رو بیاورند و ربات $a$ را تهدید به کشتن ربات $b$ کنند. (در حقیقت **دوره ۱۰۲۸ ایا** مهربان‌تر از این حرف‌ها هستند و هرگز حاضر نخواهند شد به $b$ آسیبی وارد کنند). حالا **دوره ۱۰۲۸ ایا** برای اینکه بفهمند تهدیدشان چقدر کارساز خواهد بود نیاز دارند کوتاه‌ترین رابطه فامیلی $a$ با $b$ را بدانند. # ورودی در سطر اول $n$ (تعداد کل ربات‌ها) ، $a$ و $b$ داده می‌شود. در $n$ سطر بعد دو عدد $par1_i$ و $par2_i$ که سازنده‌های ربات $i$ ام هستند، می‌آیند. همچنین اگر آن ربات توسط انسان‌ها تولید شده بود، به جای هر دو $-1$ می‌آید. $$1 \le n \le 100\ 000$$ $$-1 \le par1_i,par2_i \le i-1$$ $$ par1_i \neq par2_i $$ $$ a \neq b $$ # خروجی **کوتاه‌ترین** نسبت $a$ با $b$ را از لحاظ تعداد کلمات چاپ کنید. اگر چندین کوتاه‌ترین رابطه وجود داشت شما باید رابطه‌ای که از لحاظ **ترتیب لغت‌نامه‌ای بزرگترین** است را چاپ کنید! توجه کنید که رابطه‌ای که در خروجی بیان می‌شود باید از زبان $a$ باشد.به عنوان مثال اگر $b$ سازنده $a$ باشد جواب `pedar` است. در صورتیکه $a$ و $b$ با هم هیچ رابطه فامیلی نداشتند فقط باید ‍‍`No relationship!` را چاپ کنید. رابطه‌هایی که در خروجی می‌آیند: | رابطه | خروجی | معنی | |-------|----------|------------| | پدر | pedar | سازنده | | پسر | pesar | ساخته شده | | برادر | baradar | پسر پدر | | عمو | amoo | برادر پدر | # مثال ## ورودی نمونه ۱ ``` 10 8 4 -1 -1 -1 -1 -1 -1 2 1 -1 -1 1 5 -1 -1 1 2 6 3 5 2 ``` ## خروجی نمونه ۱ ``` 1 baradar ``` ## ورودی نمونه ۲ ``` 9 9 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 4 5 3 7 2 8 1 ``` ## خروجی نمونه ۲ ``` 2 amoo pedar ``` ## ورودی نمونه ۳ ``` 8 8 1 -1 -1 -1 -1 1 2 1 2 3 4 3 4 5 6 5 6 ``` ## خروجی نمونه ۳ ``` 3 pedar pedar pedar ``` ## ورودی نمونه ۳ ``` 2 1 2 -1 -1 -1 -1 ``` ## خروجی نمونه ۳ ``` No relationship! ```

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۱۰۲۸ ایا** می‌خواستند از سطح دانش آموزانی که در آزمون های شاز در سال ۱۳۹۷ شرکت می‌کردند مطلع شوند. اما چون **دوره ۲۸ ایا** جزییات کامل رنکینگ‌ها را منتشر نکرده بودند، **دوره ۱۰۲۸ ایا** مجبور شدند تا رمز سرورها را به‌دست آورده و با استفاده از آن به رنکینگ‌های کامل دست یافته و سطح دانش‌آموزان را ارزیابی کنند. رمز سرورهای شاز در آن زمان یک جایگشت طولانی بود. **دوره ۲۸ ایا** که در تمام امور کارهایشان را گروهی انجام می‌دادند، انتخاب رمز را نیز مستثنی نکرده بودند. در زمان **دوره ۲۸ ایا**، $m$ نفر در دست‌اندرکاران شاز وجود داشتند ($8$ نفر اصلی و $m-8$ نفر دست‌های پشت پرده!) نفر $i$ ام از این افراد معتقد بود که اگر الگوی رمز مانند جایگشت $i$ ام باشد، رمز بسیار سخت است. عملیات چیدن تعدادی عدد متمایز مثل $a_k$...$a_1$ طبق جایگشت $p_k$...$p_1$ به اینصورت تعریف می‌شود که ترتیب اعداد آرایه $a$ را طوری تغییر می‌دهیم که به ازای هر دو اندیس متمایز $ 1 \leq i,j \leq k$ داشته باشیم: $a_i<a_j$ برقرار است اگر و فقط اگر $p_i<p_j$ برقرار باشد. مثلا اگر بخواهیم اعداد $\{8,7,4,11\}$ را طبق جایگشت $\{4,2,3,1\}$ بچینیم به $\{11,7,8,4\}$ تبدیل می‌شود‌. **دوره ۲۸ ایا** طول رمز را برحسب اهمیت آن، $n$ انتخاب می‌کردند. سپس در هر مرحله یکی از افراد تعدادی عدد از اعداد باقی‌مانده (اعداد مجموعه $1$ تا $n$ که تا حالا کسی آنها را در رمز استفاده نکرده است) انتخاب می‌کرد و آن ها را طبق جایگشت خودش می‌چید‌ و سپس آن را به **انتهای** رمز به دست آمده تا‌کنون اضافه می‌کرد. همچنین یک نفر ممکن است چند بار از جایگشتش استفاده کرده و رمز را گسترش دهد. حال **دوره ۱۰۲۸ ایا** حدس‌هایی راجع به رمز سرورهای شاز زده‌اند. اما آن ها می خواهند ببینند حدسشان چقدر محتمل است. برای همین از شما می‌خواهند بپرسند که رمز مذکور به چند طریق توسط **دوره ۲۸ ایا** قابل ساخت است. # ورودی خط اول ورودی عدد $n$ و$m$ داده می‌شود. در خط بعد جایگشت $p$ داده می‌شود که نشان دهنده رمز شاز است. سپس در $m$ خط بعدی جایگشت ها به این‌صورت داده می‌شود. در ابتدا عدد $k_i$ و سپس یک جایگشت $k_i$ تایی ورودی داده می‌شود. $$1 \le n, m , k_i \le 100\ 000$$ تضمین می‌شود که مجموع $k_i$ ها از $100\ 000$ بیشتر نمی‌شود. توجه کنید که ممکن است دو نفر الگوی جایگشتی مشابهی داشته باشند! # خروجی خروجی تنها شامل یک عدد است که تعداد راه‌های مختلف تولید رمز $p$ در پیمانه $10^9+7$ می‌باشد (دو روش تولید رمز متفاوت‌اند اگر تعداد بار‌هایی که رمز گسترش داده شده در آن دو روش متفاوت باشد یا اینکه این تعداد مساوی باشد اما در مرحله‌ای مثل $i$‌ **دو جایگشت متفاوت** برای گسترش رمز استفاده شده باشند). برای فهم بهتر ورودی نمونه ۳ را ببینید. # مثال ## ورودی نمونه ۱ ``` 5 2 5 3 2 4 1 4 4 1 3 2 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` در اینجا نمی توان از نقشه اول استفاده کرد و تنها حالت ممکن ۵ بار استفاده از نقشه دوم است. ## ورودی نمونه ۲ ``` 10 2 1 2 3 4 5 6 7 8 9 10 1 1 2 1 2 ``` ## خروجی نمونه ۲ ``` 89 ``` ## ورودی نمونه ۳ ``` 5 4 5 3 4 1 2 2 1 2 2 1 2 2 2 1 3 3 1 2 ``` ## خروجی نمونه ۳ ``` 2 ``` ## ورودی نمونه ۴ ``` 3 2 1 2 3 3 1 2 3 3 1 2 3 ``` ## خروجی نمونه ۴ ``` 1 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اخیرا **دوره ۱۰۲۸ ایا** متوجه شده‌اند که **دوره ۲۸ ایا** در ضرب کردن در پیمانه مهارت فراوان داشتند. **دوره ۲۸ ایا** $n$ سوال اصلی داشتند که سختی سوال $i$ ام $a_i$ می باشد. آنها هر وقت سوال کم می آوردند یک زیرمجموعه از سوالات اصلی را با هم ترکیب می‌کردند و سوال دیگری بدست می‌‌آوردند که سختی آن برابر با ضرب سختی سوالات زیر مجموعه در پیمانه $p$ بود (دقت کنید که به طور خاص اگر آنها زیرمجموعه تهی را انتخاب می‌کردند **سوالی با سختی ۱** به دست می‌آوردند). حالا **دوره ۱۰۲۸ ایا** سوالات اصلی را به طریقی گیر آوردند و می‌خواهند خفونت خود را به جهانیان ثابت کنند. بنابرین می‌خواهند تمام سوالات با سختی‌های متفاوتی که **دوره ۲۸ ایا** می‌توانستند طرح کنند را حل کنند اما قبل از آن از شما می خواهند بگویید به ازای هر سختی از $1$ تا $p-1$ آیا **دوره ۲۸ ایا** می‌توانستند سوالی با این سختی تولید کنند یا خیر. ضمنا ما از منبع موثقی می‌دانیم که **p عددی اول است**. # ورودی در خط اول عدد $n$ , $p$ می‌آید. در خط بعد $n$ عدد می‌آید که $i$ امین آن $a_i$ می‌باشد. $$1 \le n, p \le 100\ 000$$ $$1 \le a_i \le p-1$$ # خروجی یک رشته $p-1$ بیتی دودویی خروجی دهید که بیت $i$ امش‌ (از چپ) ۱ است اگر و فقط اگر بتوان سوالی با سختی $i$ تولید کرد. # مثال ## ورودی نمونه ۱ ``` 3 7 3 3 3 ``` ## خروجی نمونه ۱ ``` 111001 ``` ## ورودی نمونه ۲ ``` 5 19 16 10 2 2 4 ``` ## خروجی نمونه ۲ ``` 110100111100110100 ```

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- **دوره ۱۰۲۸ ایا** که به این حجم از فعالیت‌های شاز در دوره ۲۸ مشکوک شده بودند، دریافتند که **دوره ۲۸ ایا** کپی می‌کردند! با بررسی‌های فراوان معلوم شد که **دوره ۲۸ ایا** برای این کار ابتدا $n$ چیز روی صفحه می‌نوشتند و سپس در شب $i$ ام بازه $l_i$ تا $r_i$ را در بین چیز $k_i$ ام و $k_i+1$ ام کپی می‌کردند‌‌. فرض کنید تعداد چیز ها قبل از انجام عملیات کپی در شب $i$ ام $N_i$ باشد. یعنی: $$\ N_1=n \ , \ N_i+r_i-l_i+1=N_{i+1} \ $$ می دانیم اگر $k_i=0$ باشد در ابتدای چیز‌ها کپی می‌کردند و اگر $k_i=N_i$ در انتهای چیز‌ها کپی می‌کردند‌). **دوره ۲۸ ایا** بعد از هر کپی شبانه خود متن بدست آمده را به عنوان پست در بلاگ شاز متنشر می‌کردند! (**دوره ۱۰۲۸ ایا** از فعالیت‌های شاز مات و مبهوت مانده بودند، سعی داشتند با خذعبلات منتشر شده از ذهن کثیفشان! خود را توجیه کرده و کار‌های **دوره ۲۸ ایا** را بی‌ارزش سازند). **دوره ۱۰۲۸ ایا** توانسته بودند (‌به خیال خام خود!) نحوه کپی کردن پست‌ها را بدست آورند. آنها ارزش مطالب **دوره ۲۸ ایا** را می‌دانستند. اما دیدند که فعالیت شاز آنقدر زیاد بوده که در سال ۲۳۹۷ نیز اگر تمام توان خود را جمع می‌کردند، نمی‌توانستند $10^{18}$ چیز تشکیل‌دهنده پست شاز را تفسیر کنند. (برای این که بفهمید $10^{18}$ چقدر بزرگ است، کافیست تعداد میکرو ثانیه‌های مانده تا سال ۲۳۹۷ را حساب کنید!) به همین خاطر تصمیم گرفتند به جمع چیز‌های تشکیل‌دهنده پست‌های شاز به پیمانه $10^9+7$ بسنده کنند. # ورودی در سطر اول $n$ می‌آید و در سطر دوم یک آرایه $n$ تایی $a_i$ می‌آید که همان چیز‌های اولیه هستند. در سطر سوم $q$ که تعداد پست‌های اولیه شاز است می‌آید و در $q$ سطر بعد در هر سطر $l_i$ و $r_i$ و $k_i$ می‌آیند. $$ 0 \leq a_i \leq 10^9 $$ $$ 1 \leq n,q \leq 50\ 000$$ $$ 1 \leq l_i \leq r_i \leq N_i \leq 10^{18} $$$$ 0 \leq k_i \leq N_i $$ # خروجی در $q$ سطر در هر سطر جمع چیز‌های پست شاز در آن شب (بعد از هر کپی کردن) را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 5 1 3 6 4 6 5 2 4 1 2 8 2 9 13 13 1 13 12 8 25 3 ``` ## خروجی نمونه ۱ ``` 33 65 90 145 223 ``` ## ورودی نمونه ۲ ``` 5 523678577 195438412 597619564 103402540 338592606 5 2 2 0 1 6 6 3 7 4 7 16 3 8 25 24 ``` ## خروجی نمونه ۲ ``` 954170104 908340201 338831721 33837909 970289194 ```