+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باتری تلفن همراه مرد مالیاتچی‌ تمام شده‌است. می‌دانیم تلفن مرد مالیاتچی برای اینکه از $i$ درصد شارژ به $i + 1$ درصد برسد $i + 1$ دقیقه زمان می‌برد. حال ما از شما می‌خواهیم با دریافت عدد $k$ بگویید چند دقیقه طول می‌کشد که تلفن مرد مالیاتچی از صفر درصد شارژ به $k$ درصد شارژ برسد. # ورودی در یک خط عدد $k$ به شما داده می‌شود. $$ 1 \le k \le 100$$ # خروجی در یک خط مجموع دقایقی که طول می‌کشد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 3 ``` ## خروجی نمونه ۲ ``` 6 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، به تازگی به رشته‌ی صنایع علاقه پیدا کرده است. به همین دلیل تصمیم گرفته است تا در مورد این رشته تحقیق کند. او به افراد مختلفی مراجعه می‌کند و هرکدام یک مقداری اطلاعات به او می‌دهند. او به اندازه‌ی مقدار اطلاعاتی که از اشخاص می‌گیرد متعجب می‌شود. مثلا اگر یک عدد اطلاعات بگیرد می‌گوید `Wow!`، اگر دوتا اطلاعات بگیرد می‌گوید`Woow!` و به همین شکل مقدار کشیدن کلمه(تعداد `o` ها) زیاد می‌شود. حالا شما باید بگویید که اگر یک نفر به اندازه‌ی $n$ به مهدی اطلاعات بدهد، ما باید انتظار چه کلمه‌ای را از او داشته باشیم.  # ورودی در تنها سطر ورودی یک عدد طبیعی $n$ به شما داده شده است که نمایانگر مقدار اطلاعات داده‌شده به مهدی است. $$ 1 \le n \le 10 $$ # خروجی خروجی شامل یک کلمه است،‌ که نشان‌دهنده‌ی کلمه‌ ایست که مهدی بعد از شنیدن اطلاعات راجع به رشته‌ی صنایع می‌گوید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` Wow! ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` Woow! ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- برنامه‌ای بنویسید که با ورودی گرفتن عدد $n$، همه‌ی زیرمجموعه‌های مجموعه‌ی $\{ 1, 2, 3, ..., n \}$ را چاپ کند. این زیرمجموعه‌ها را به ترتیب الفبایی مرتب کنید؛ یعنی ابتدا عناصر هر زیرمجموعه را مرتب کنید و سپس به آن‌ها مانند کلمات نگاه کنید و به ترتیبی که در لغت‌نامه می‌آیند مرتب‌شان کنید. تلاش کنید که این کار را تنها به وسیله‌ی تابع بازگشتی انجام دهید؛ یعنی طوری پیاده‌سازی کنید که این مجموعه‌ها به همین ترتیب تولید و چاپ شوند. (به جای این که ابتدا همه را تولید کرده و سپس مرتب کنید.) برای آشنایی با قالب خروجی دادن به نمونه‌ها توجه کنید. # ورودی ورودی تنها شامل یک خط است که در آن یک عدد طبیعی $n$ آمده است. $$1 \le n \le 15$$ # خروجی خروجی برنامه‌ی شما باید شامل $2^n$ خط باشد که در هر خط یک زیرمجموعه چاپ شود. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` {} {1} ``` ## ورودی نمونه ۲ ``` 3 ``` ## خروجی نمونه ۲ ``` {} {1} {1, 2} {1, 2, 3} {1, 3} {2} {2, 3} {3} ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علیش که جدیدا نمی‌تونه خوب بنویسه، از پاشا می‌خواد که جمله‌ای که تو ذهنش هست رو واسش بنویسه. پاشا هم که می‌خواد استیل بیاد تصمیم می‌گیره که این جمله رو تایپ کنه اما از اون‌جایی که حتی بلد نیست تایپ کنه، وقتی داره جمله رو می‌نویسه به‌جای دکمه بک‌اسپیس(پاک کردن آخرین حرف نوشته شده **در صورت وجود**) دکمه `=` رو می‌زنه. (دقت کنید که اگر در ابتدای جمله بک‌اسپیس زده شه هیچ اتفاقی نمی‌افته!) پاشا هم که نمی‌خواد زحماتش حروم بشه و جلوی علیش ضایع بشه از شما کمک می‌خواد و به شما رشته‌ای که تایپ کرده رو میده و ازتون می‌خواد براش رشته اصلی رو بنویسید. # ورودی در تنها خط ورودی یک رشته $S$ آمده‌است که همان رشته نوشته‌شده توسط پاشا است. $$1 \le |S| \le 100\ 000$$ + رشته $S$ تنها از حروف کوچک انگلیسی و `=` تشکیل شده‌است. # خروجی خروجی باید تنها شامل یک خط باشد که همان رشته‌ای است که علیش می‌خواسته تایپ شود. # مثال ## ورودی نمونه ۱ ``` sall=am ``` ## خروجی نمونه ۱ ``` salam ``` ## ورودی نمونه ۲ ``` testtwoo===wo ``` ## خروجی نمونه ۲ ``` testtwo ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پوپک از خواب بیدار می‌شود... به یاد می‌آورد که خوابی دیده است اما جزییات این خواب در خاطرش نیست... پوپک می‌داند که او در خوابش دو کیسه تیله داشته است که در هر کیسه حداقل یک تیله بوده است. پوپک می‌داند که تعداد تیله‌های کیسه اول مقسوم‌علیهی از عدد $a$ بوده و تعداد تیله‌های کیسه دوم مقسوم علیهی از عدد $b$ بوده است. همچنین پوپک به یاد دارد که دو کیسه‌اش خیلی سنگین نبودند و در مجموع حداکثر $x$ تیله در دو کیسه قرار داشته است. در همین هنگام پوپک، توک را می‌بیند و ماجرا را برای او تعریف می‌کند. توک نیز خیلی سریع تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را می‌شمارد و این تعداد را به او می‌گوید... در همین هنگام توک یه دل نه صد دل عاشق پوپک می‌شود ... # ورودی در تنها خط ورودی به ترتیب سه عدد $a$ و $b$ و $x$ آمده است. $$1 \le a, b\le 1\ 000$$ $$2 \le x \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را چاپ کنید. ## ورودی نمونه ۱ ``` 2 2 2 ``` ## خروجی نمونه ۱ ``` 1 ``` تنها حالت ممکن این است که در هر دو کیسه دقیقا $1$ تیله قرار گرفته باشد. ## ورودی نمونه ۲ ``` 7 7 14 ``` ## خروجی نمونه ۲ ``` 4 ``` چهار حالت مختلف برای تعداد تیله‌های در کیسه $(1, 1)$ و $(1, 7)$ و $(7, 1)$ و $(7 , 7)$ هستند.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- برنامه‌ای بنویسید که سه عدد صحیح مثبت را به عنوان ورودی از کاربر دریافت کند و در صورتی که امکان ساخت مثلث قائم الزاویه با طول اضلاع داده شده وجود داشته باشد `YES` و در غیر این صورت `NO` چاپ کند. # ورودی ۳ عدد صحیح در ۳ خط ورودی به شما داده می‌شود. # خروجی چنانچه می‌توانیم با ۳ عدد ورودی مثلث قائم الزاویه‌ای بسازیم `YES` در غیر اینصورت `NO` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 4 3 ``` ## خروجی نمونه ۱ ``` YES ``` ## ورودی نمونه ۲ ``` 8 7 10 ``` ## خروجی نمونه ۲ ``` NO ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- زانا سالی یک بار یک جشن خاص برگزار می‌کند و تعدادی از دوستانش را به این جشن دعوت می‌کند. اسم این جشن «جشن هدیه‌ها» است! هر فردی که در این جشن شرکت می‌کند مقداری پول به همراه خود دارد و به تعدادی از دوستانش هدیه می‌دهد. روش هدیه دادن در این جشن کمی عجیب است! هر کدام از افراد یک لیست هدیه دارد که در آن لیست، نام تعدادی از دوستانش که در جشن شرکت کرده‌اند نوشته شده است و تمام پولی که همراه دارد را بین افراد این لیست به طور مساوی تقسیم می‌کند و این پول را به آنها هدیه می‌دهد! چون پول اعشاری (کوچکتر از یک) نداریم ، این تقسیم‌ها تقسیم صحیح هستند و اگر تقسیم پول بین اعضای لیست باقیمانده‌ای داشته باشد ، فرد هدیه دهنده این باقیمانده را برای خود نگه می‌دارد. به طور مثال اگر ساینا ۱۱ واحد پول داشته باشد و در لیست او فقط سه نفر باشند ، به هر کدام از آنها ۳ واحد پول میدهد و ۲ واحد از پول خود را برای خود نگه می‌دارد. حال شما برنامه‌ای بنویسید که پس از گرفتن اسامی شرکت کنندگان، مقدار پول اولیه‌ی هر کدام و لیست هدیه هر کس، مشخص کند که هرکسی چقدر سود یا زیان کرده است! # ورودی + خط 1 : عدد `n` که برابر است با تعداد شرکت کنندگان در جشن. + خط 2 تا `n+1` : در هر خط اسم یکی از شرکت کنندگان. + خط `n+1` الی آخر : از این خط به بعد ورودی به `n` دسته تقسیم می‌شود که هرکدام مطابق زیر است: خط اول نام فردی که قرار است هدیه بدهد. در خط دوم دو عدد می‌آید: عدد اول مقدار پول آن فرد، عدد دوم `(k)` تعداد افراد موجود در لیست هدیه‌ی آن فرد در `k` خط بعدی در هر خط نام یکی از افراد موجود در لیست هدیه‌ی آن فرد. می‌توانید فرض کنید نام هر دو نفر از افراد شرکت‌کننده در جشن متمایز است و $$ 2 \leq n \leq 10$$ # خروجی در خروجی باید `n` خط چاپ کنید که در هر ابتدای هر خط نام هر شخص و بعد از آن مقدار سود او آورده شود. (اگر آن شخص ضرر کرده است، باید منفی مقدار ضرر چاپ شود.) ترتیب نام‌ها در خروجی باید مانند ترتیب نام‌ها در خطوط `2` تا `n+1` ورودی باشد. # مثال ## ورودی نمونه ``` 5 dave laura owen vick amr dave 200 3 laura owen vick owen 500 1 dave amr 150 2 vick owen laura 0 2 amr vick vick 0 0 ``` ## خروجی نمونه ``` dave 302 laura 66 owen -359 vick 141 amr -150 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علیش که دیگه هدفی واسه زندگی‌کردن نداره تصمیم گرفته مریض‌شه. اما آقا مجید (که داره دکتر می‌شه) بهش گفته که باید $n$ تا قرص بخوره. علیش هم که به این سادگی نمی‌خواد قبول کنه $m$ تا شرط واسه قرص خوردن داره که هر شرط شامل $a_i$ و $b_i$ است که یعنی قرص $a_i$ام رو باید قبل قرص $b_i$ام بخوره. هم‌چنین $n$ شرط دیگه هم داره که قرص $i$ام باید حداقل $l_i$امین و حداکثر $r_i$امین قرصی باشه که می‌خوره. یه ترتیبی به علیش بدید که اگه به این ترتیب قرصاشو بخوره همه شرط‌ها برقرار باشه. # ورودی در خط اول $n$ و $m$ آمده که با یک فاصله از هم جدا شده‌اند. در $n$ خط بعدی $l_i$ و $r_i$ ها آمده‌است. در $m$ خط بعدی دو عدد $a_i$ و $b_i$ آمده که با فاصله از هم جدا شده اند و یعنی قرص $a_i$ام باید قبل قرص $b_i$ام خورده شود. $$1 \le n \le 200\ 000$$ $$1 \le m \le 300\ 000$$ $$1 \le l_i \le r_i \le n$$ $$ 1 \le a_i \le b_i \le n$$ # خروجی در خروجی $n$ خط که شامل جایگشتی از اعداد ۱ تا $n$ است و تمام شروط در آن برقرار است چاپ شود. اگر چند جواب وجود داشت یکی را به دلخواه چاپ نمایید. اگر ترتیبی وجود نداشت که همه شرط‌ها در آن برقرار باشند `-1` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 2 2 1 4 1 4 1 4 1 2 1 3 3 4 2 4 ``` ## خروجی نمونه ۱ ``` -1 ``` ## ورودی نمونه ۲ ``` 4 4 1 1 2 4 2 4 4 4 1 2 2 3 3 4 1 4 ``` ## خروجی نمونه ۲ ``` 1 2 3 4 ``` ## ورودی نمونه ۳ ``` 4 3 1 1 1 4 2 3 1 4 1 2 4 3 3 2 ``` ## خروجی نمونه ۳ ``` 1 4 3 2 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از مدت‌ها که لیته توانست با موفقیت چالش خوش‌اندام شدن را تا حدودی پشت سر بگذارد، فیته نیز کم‌کم به او علاقه‌مند شد و امروز آن‌ها می‌خواهند به اولین قرار خود بروند. لیته در نقطه $a$ شهر زندگی می‌کند و فیته نقطه $b$ را برای اولین قرار انتخاب کرده‌است. در این شهر دو نوع قطار برای جا‌به‌جایی وجود دارد: * نوع اول: نقطه $x$ و $x + 1$ را با یک مسیر دو طرفه به هم متصل می‌کند. ( به ازای هر $x$ صحیح ) * نوع دوم: نقطه $k \times x$ و $k \times (x +1)$ را با یک مسیر دوطرفه به هم متصل می‌کند. ( به ازای هر $x$ صحیح و $k$ داده شده در ورودی )  هم چنین می‌دانیم فاصله طی کردن یک مسیر بین دو نقطه به ازای هر‌نوع قطار دقیقا یک دقیقه است. وظیفه شما به عنوان دوست و رفیق لیته این است که به او بگویید زودترین زمان ممکن رسیدن لیته به محل قرار چقدر است. # ورودی ورودی تنها شامل یک سطر است که در آن به ترتیب سه عدد صحیح $k$ و $a$ و $b$ با فاصله از هم آمده‌است. $$-10^9 \le a, b \le 10^9$$ $$1 \le k \le 10^9$$ # خروجی در تنها سطر خروجی زودترین زمان رسیدن لیته به محل قرار را چاپ کنید. ## ورودی نمونه ``` 4 1 10 ``` ## خروجی نمونه ``` 5 ``` نمونه‌ی بالا همان تصویر موجود در صورت سوال است؛ مسیر بهینه با ۵ سفر در تصویر پررنگ شده است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی $n$ خانه وجود دارد و در هر خانه **حداکثر یک** تروریست زندگی می‌کند. برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، $m$ پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس $i$-ام خانه‌های $l_i$ تا $r_i$ را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند. مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید. # ورودی در سطر اوّل ورودی به ترتیب دو عدد $n$ و $m$ می‌آید. در سطر $i$-ام از $m$ سطر بعد، دو عدد $l_i$ و $r_i$ آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس $i$-ام زیر نظر گرفته است. $$1 \le l_i \le r_i \le n$$ $$1 \le n, m \le 100\ 000$$ # خروجی در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند. # مثال ## ورودی نمونه ۱ ``` 5 2 1 3 2 4 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 6 3 2 4 3 5 2 5 ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- مسئله‌ای به شما داده شده است که بایستی به صورت یک مسئله $CSP$ آن را فرموله کرده و پیاده‌سازی نمایید. فرض کنید گرافی در اختیار داریم که گره‌های آن می‌توانند هر یک از اشکال مثلث، مربع، پنج ضلعی، شش ضلعی و یا دایره باشند. می‌خواهیم به هر گره از این گراف، یک عدد بین ١ تا ٩ نسبت دهیم به صورتی که شروط زیر برقرار باشند: + عدد منتسب به هر گره مثلثی شکل، برابر سمت چپ ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل مربع، برابر سمت راست ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل پنج ضلعی، برابر سمت چپ ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل شش ضلعی، برابر سمت راست ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + محدودیتی برای گره‌های دایره‌ای شکل وجود ندارد. شکل یک گراف نمونه با اعداد منتسب شده به هر گره را نشان می‌دهد. از شما خواسته شده است تا با دریافت مشخصات گراف، اعداد منتسب به گره‌های آن را پیدا کنید.  # ورودی خط اول ورودی عدد $T$ است که تعداد تست‌ها را نشان می‌دهند. خط اول هر تست، شامل اعداد $V$ و $E$ است که اولی نشان دهنده تعداد گره‌ها و دومی نشان دهنده تعداد یال‌های گراف است. در خط بعد $V$ کاراکتر از بین یکی ͬاز کاراکترهای `T`برای مثلث، `S` برای مربع، `P` برای پنج ضلعی، `H` برای شش ضلعی و `C` برای دایره، که با یک فاصله از هم جدا شده‌اند می‌آید که کاراکتر $i$ام، شکل گره $i$ام را مشخص می‌کند (0 ≥ $i$). پس از آن، $E$ خط به صورت ‍‍`i j` می‌آید. که نشان می‌دهد یالی میان گره $i$ام و گره $j$ام وجود دارد. نمونه ورودی متناظر با شکل در ادامه آمده است. # خروجی به ازای هر تست، یک خط خروجی می‌آید که شامل $V$ عدد بین ١ تا ٩ است که با فاصله از هم جدا شده اند و عدد $i$ام، مقدار منتسب به گره $i$ام را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 1 9 8 C P H S S H H T C 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ``` ## خروجی نمونه ۱ ``` 9 1 7 6 8 3 5 2 4 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علیش که دیگه از این زندگی خسته‌شده داره میره اونور و امشب گودبای پارتیشه. پاشا هم که علاقه زیادی به پیش‌خدمت بودن داره پیش‌خدمت دم دره و به علیش کمک می‌کنه. مهمونی ساعت `00:00` شروع میشه و تا ساعت `23:59` طول می‌کشه. وظیفه پاشا اینه که هر کسی که میاد تو مهمونی و یا بیرون می‌ره، رو یه تیکه کاغذ اول اسم اون نفرو، بعدش ساعت اون موقع و بعدش `+` یا `-` (که `+` یعنی اومده و `-` یعنی رفته) رو می‌نویسه و کاغذو می‌ندازه تو کیسه. علیش بعد این که مهمونی تموم‌شد به این فکر می‌کنه که تو چه زمانی مهمونی شلوغ‌ترین موقع ممکن بوده و چون وسط مهمونی حواسش به دور و برش نبوده این سوالو از پاشا می‌پرسه. پاشا هم که یه پیش‌خدمت سادست همه‌چی رو یادش رفته و فقط اطلاعات روی کاغذها رو داره. از طرفی اون نمی‌خواد علیش‌رو ناراحت کنه و از شما می‌خواد تا با گرفتن اطلاعات روی کاغذها بگید که تو چه زمانی مهمونی شلوغ‌ترین حالت رو داشته. (تعداد افرادی که در یک زمان در مهمانی هستند بعد از تمام داخل و خارج شدن ها در آن زمان حساب می‌شود.) # ورودی در خط اول $n$ تعداد تیکه کاغذها آمده سپس در $n$ خط بعدی اسم و ساعت و یکی از کاراکترهای `+` یا `-` آمده‌است. $$1 \le n \le 100\ 000$$ + فرمت تمام ساعت‌ها به‌شکل `HH:MM` است. + اسم رشته‌ای تشکیل‌شده از حروف کوچک انگلیسی است. + تضمین می‌شود جمع طول اسم‌ها حداکثر $500\ 000$ باشد. + تضمین می‌شود اگر کسی وارد مهمانی شود، قبل از آن در مهمانی نبوده و اگر هم خارج‌شود قبل از آن در مهمانی بوده‌است. # خروجی در تنها خط خروجی شلوغ‌ترین ساعت مهمونی رو با فرمت `HH:MM` چاپ‌کنید. در صورت وجود چندین جواب یکی‌را به دلخواه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 ali 23:32 - ali 20:12 + ``` ## خروجی نمونه ۱ ``` 21:15 ``` هر ساعتی بین $20:12$ تا $23:31$ نیز می‌تواند جواب باشد. ## ورودی نمونه ۲ ``` 4 alish 16:15 + pasha 22:34 - alish 23:56 - pasha 21:21 + ``` ## خروجی نمونه ۲ ``` 21:33 ```

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شما بایستی از الگوریتم $A*$ برای حل مسئله راه‌بندان استفاده کنید. در این مسئله، یک خودروی قرمز رنگ به همراه چند خودروی دیگر در یک پارکینگ مشابه شکل پارک شده‌اند. می‌خواهیم با جابجا کردن خودرو‌‌ها، برای خودروی قرمز رنگ که بین سایر خودروها گرفتار شده است، راهی باز کرده و آن را از پارکینگ خارج نماییم. همه‌ی خودروها در این پارکینگ به صورت افقی و عمودی پارک شده‌اند. از آنجایی که اکنون امکان دور زدن وجود ندارد، خودروهایی که به صورت افقی قرار دارند تنها می‌توانند به چپ و راست حرکت کرده و خودروهای عمودی نیز فقط امکان بالا و پایین رفتن دارند.  هدف این است که با کمترین تعداد حرکت، خودروی قرمز رنگ را که همواره به صورت افقی و روبروی درب خروجی (که در ضلع شرقی پارکینگ قرار دارد) پارک شده است، از پارکینگ خارج نماییم. در هر حرکت، یک خودرو می‌تواند در راستایی که قرار دارد به هر تعداد خانه دلخواه جابجا شود، مشروط بر اینکه با سایر خودروها و یا دیوار برخورد نکند. همچنین خارج کردن خودروهای دیگر به جز خودروی قرمز رنگ از پارکینگ مجاز نمی‌باشد. # ورودی ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد $T$ است که تعداد پارکینگ‌ها را مشخص می‌کند. پس از آن مشخصات $T$ پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد $N$ ،$M$ و $V$ قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص می‌کند. $V$ خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد $R$ و $C$ قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص می‌کنند. در ادامه راستای خودرو با یک کاراکتر $h$ برای افقی و یا $v$ برای عمودی مشخص می‌شود. در انتهای خط نیز عدد $L$ طول خودرو را نشان می‌دهد. لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر $N$ و ستون $M$ قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است. # خروجی به ازای هر پارکینگ، برنامه باید کمترین تعداد حرکات که منجر به خروج خودروی قرمز رنگ از پارکینگ می‌شود را چاپ کند. نمونه خروجی برای شکل در زیر آمده است. ## ورودی نمونه ``` 1 6 6 13 3 1 h 2 1 1 v 2 1 2 v 2 1 4 h 3 2 3 h 2 2 5 h 2 3 4 v 2 4 2 v 2 5 3 h 2 5 5 v 2 5 6 v 2 6 1 h 2 6 3 h 2 ``` ## خروجی نمونه ``` Test #1: 16 ```

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از تلاش‌های ناموفق لیته برای خوشحال کردن فیته، وی تصمیم گرفت خودش و فیته را در برنامه بعدی گروه کوه دانشگاه ثبت‌نام کند تا این سفر چندروزه باعث بهبود روابطشان شود. برنامه بعدی گروه کوه در منطقه‌ی **بقمچگاه** برگزار خواهد شد که استراحت‌گاه‌های آن و راه‌های ارتباطی بین آن‌ها مثل یک گراف جهت‌دار هستند. در این گراف: * از یک استراحت‌گاه به یک استراحت‌گاه **دیگر** حداکثر یک راه مستقیم وجود دارد. (ممکن است بین دو استراحت‌گاه دو راه متفاوت در خلاف جهت یکدیگر وجود داشته باشد) * از یک استراحت‌گاه به خودش راه مستقیمی وجود ندارد. * **ممکن** است در گراف دور وجود داشته باشد. اما دقیقا یک روز قبل از حرکت به سمت بقمچگاه، اخبار ناخوشایندی به لیته می‌رسد مبنی بر این که طی روزهای برنامه در این منطقه ییلاقی شاهد زمین‌لرزه‌ها و پس‌لرزه‌هایی خواهیم بود. * به طور واضح تر این‌طور خواهد بود که به ازای هر استراحت‌گاه در بعضی از روزها در آن استراحت‌گاه لرزشی اتفاقی می افتد. اولین لرزش در یک استراحت‌گاه یک زمین‌لرزه است و همه‌ی لرزش‌های بعدی پس‌لرزه هستند. ( تفاوت زمین‌لرزه و پس‌لرزه در پایین توضیح داده شده است ) متاسفانه اگر در یکی از استراحت‌گاه‌های این منطقه زمین‌لرزه اتفاق بیفتد، همه افراد ساکن در این استراحت‌گاه به دیار باقی خواهند شتافت. و اگر در استراحت‌گاهی پس‌لرزه بیاید، افراد ساکن باید به یکی از استراحت‌گاه‌هایی که به آن راه خروج مستقیم دارند فرار کنند. این فرار **دقیقا یک روز** طول می‌کشد. **توجه** کنید در صورتی که در استراحت‌گاهی پس‌لرزه بیاید و آن استراحت‌گاه به استراحت‌گاه دیگری راه خروج مستقیمی نداشته‌باشد، ناچار جان به جان‌آفرین تسلیم خواهند کرد. نکته‌ی حائز اهمیت این است که لیته و فیته در این سفر در کنار هم خواهند بود و هر وقت ناچار به فرار شوند، یکی از استراحت‌گاه های ممکن را باهم انتخاب می‌کنند و به آن‌جا می‌روند. یعنی تا لرزه‌ای رخ ندهد در جای خود ساکن خواهند ماند. نیمه‌های شب لیته با اتصال به روح مهرسا از زمان همه زمین‌لرزه‌ها و پس‌لرزه‌ها باخبر می‌شود و حالا مدام سوالاتی به ذهنش می‌رسند که اگر در روز $t$-ام اردو در استراحت‌گاه شماره $x$ باشند، آیا ممکن است تا آخر اردو زنده بمانند یا خیر. طبیعتا شما باید در حل این مسئله به او کمک کنید. # ورودی سطر اول ورودی شامل سه عدد طبیعی $n$ و $m$ و $q$ است که به ترتیب نشان‌دهنده تعداد استراحت‌گاه‌ها، تعداد راه‌های یک‌طرفه بین آن‌ها و تعداد سوالات ذهن لیته هستند.$$1 \le n, m, q \le 400\ 000$$ در $i$-امین سطر از $n$ سطر بعد اطلاعات لرزش‌های استراحت‌گاه شماره $i$ آمده است، به این صورت که در ابتدا عدد $k$ آمده است که نشاندهنده تعداد لرزش‌های شهر $i$ است و به دنبال آن $k$ عدد مثل $t$ به ترتیب صعودی اکید آمده اند که نشاندهنده‌ی روزهایی هستند که در شهر $i$ لرزش اتفاق افتاده است. * اولین لرزش هر شهر یک زمین‌لرزه است و بقیه لرزش‌ها در آن شهر پس‌لرزه هستند. * تضمین می‌شود که زمان تمامی لرزش‌ها متفاوت هستند. یعنی در یک زمان در دو استراحت‌گاه لرزش اتفاق نمی افتد. $$0 \le k \le 400\ 000$$ $$1 \le t \le 10^9$$ * هم‌چنین تضمین می‌شود در مجموع تعداد لرزش ها کمتر مساوی $400\ 000$ می‌باشد. در هر یک از $m$ سطر بعد دو عدد $v$ و $u$ آمده‌است که نشان‌دهنده وجود مسیر یک‌طرفه از استراحت‌گاه شماره $v$ به استراحت‌گاه شماره $u$ است. $$1 \le v, u \le n$$ در هر یک از $q$ سطر بعد به ترتیب دو عدد $x$ و $t$ آمده‌است که نشان‌دهنده یکی از سوالات ذهن لیته است. (آیا اگر آنها در روز $t$ در استراحت‌گاه شماره $x$ باشند می‌میرند یا زنده خواهند ماند) $$1 \le t \le 10^9$$ $$1 \le x \le n$$ # خروجی به ازای هر سوال ذهن لیته، اگر پاسخ سوال این است که زنده خواهند ماند کلمه `Alive` را چاپ کنید و در غیر این‌صورت کلمه `Dead` را چاپ کنید. ## ورودی نمونه ``` 4 4 4 2 2 4 3 1 5 7 1 6 1 10 1 2 2 3 3 1 2 4 2 5 2 6 1 4 1 5 ``` ## خروجی نمونه ``` Dead Alive Dead Alive ``` نقشه استراحتگاه مربوط به ورودی نمونه را در شکل زیر می‌بینید.  اگر در زمان ۵ در استراحت‌گاه ۲ باشند (پرسش اول) قطعا می‌میرند زیرا چه به استراحت‌گاه ۳ (در زمان ۶) بروند چه استراحت‌گاه ۴ (در زمان ۱۰) می‌میرند. اگر در زمان ۶ در استراحت‌گاه ۲ باشند (پرسش دوم) می‌توانند در زمان ۷ پس لرزه می‌آید و آنها با رفتن به استراحت‌گاه ۳ زنده می‌مانند. زیرا در زمان ۸ به استراحت‌گاه ۳ می‌رسند و دیگر زلزله‌ای نمی‌آید. اگر در زمان ۴ در استراحت‌گاه ۱ باشند (پرسش سوم) مجبورند به استراحت‌گاه ۲ بروند و مانند پرسش اول می‌میرند. اگر در زمان ۵ در استراحت‌گاه ۱ باشند (پرسش چهارم) زلزله‌ای نمی‌آید و همانجا زنده می‌مانند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ممل علیشو مجبور کرده که $n$ تا رشته از حروف کوچک انگلیسی رو، رو یه کاغذ بنویسه. ممل می‌خواد این کاغذو بذاره جلو پاشا و بهش بگه با این کلمه‌ها یه رشته‌ی پالیندروم(رشته ای که خودش با برعکس برابره مثل `abba`) بنویسه. پاشا باید حداقل یکی از این رشته‌هارو استفاده کنه و می‌تونه یه رشته رو چند بار استفاده کنه و به هر ترتیبی که خواست اونارو بچسبونه به هم و بنویسه و نتیجه باید رشته‌ای پالیندروم بشه. ممل به تعداد حروفی که پاشا در رشته آخر نوشته علیشو می‌زنه. علیش رشته‌هایی که نوشته بودو یادشه و می‌خواد بدونه حداقل چند بار کتک می‌خوره. حداقل تعداد کتک‌هایی که علیش می‌خوره چند تاست؟‌ اگه پاشا نتونه رشته پالیندروم بسازه ممل علیشو ماچ می‌کنه که معادل `-1` بار(!) کتک خوردنه. # ورودی در خط اول $n$، و در $n$ خط بعدی رشته هایی که علیش نوشته آمده. تضمین می‌شود رشته‌ها فقط از حروف کوچک انگلیسی تشکیل شده باشند و جمع طول آنها حداکثر $3\ 000$ باشد. $$1 \le n \le 3\ 000$$ # خروجی در خروجی تنها حداقل تعداد بار‌هایی که علیش کتک می‌خوره رو چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 ps as sp ``` ## خروجی نمونه ۱ ``` 4 ``` \**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داره `pssp` است. ## ورودی نمونه ۲ ``` 4 abb ba bba abaa ``` ## خروجی نمونه ۲ ``` 5 ``` \**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داشته باشه `abbba` است. ## ورودی نمونه ۳ ``` 3 abbs sbbx we ``` ## خروجی نمونه ۳ ``` -1 ``` \**پاشا نمی‌تونه رشته پالیندرومی بسازه.