به مناسبت حماسه‌ی نهم دی، تمام ارگان‌های دولتی به صورت خودجوش تصمیم به حضور در راهپیمایی گرفته‌اند. هر کدام از این ارگان‌ها تصمیم گرفته‌است کد ملی کارمندان خود را روی یک پلاکارد بنویسد تا مردم از حماسی بودن آنها مطلع شوند. از طرفی از آنجا که سیاست‌های اشتغال‌زایی دولت تأکید بر تک‌شغله بودن مدیران دولتی دارد، مأمورین مبارزه با فساد بین جمعیت راه می‌افتند و هر کسی که اسمش روی دو پلاکارد باشد را گوش‌مالی می‌دهند و املاک نجومی وی را بررسی می‌کنند. حال غلام می‌خواهد بداند که کدام ارگان‌ها اسم وی را رد کرده‌اند که شر نشود. به وی کمک کنید.

ورودی🔗

در خط اول، $i$ و $m \leq 10^5$ به ترتیب معرف کد ملی غلام و تعداد ارگان‌های دولتی می‌باشد. در $m$ خط بعدی، در هر خط ابتدا اسم ارگان، سپس تعداد کارمندان آن و درنهایت کد ملی کارمندان آن ارگان آمده‌است. (کد ملی هر فرد به غیر از غلام عددی منحصربه‌فرد بین $0$ و $10^9$ است. شماره‌ی غلام $1$ نیست زیرا $1$ فردی بسیار ساکت است؛ پس شماره‌ی وی بین $0$ و $10^9$ به جز $1$ است.) اسم هر ارگان حداکثر ۱۰۰ حرفی است و تنها از حروف بزرگ و کوچک انگلیسی تشکیل شده‌است.

خروجی🔗

در تنها خط خروجی اسم همه‌ی ارگان‌هایی که غلام در آن‌ها استخدام شده‌است را به ترتیبی که در ورودی آمده‌اند بنویسید.

ورودی نمونه ۱

123456 5
Farhangestan 1 123456
Majles 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
BonyadeIranshenasi 1 123456
ShorayeAliyeEnghelabeFarhangi 2 1 123456
MajmaeTashkhiseMaslehateNezam 2 123456 1

خروجی نمونه ۱

Farhangestan BonyadeIranshenasi ShorayeAliyeEnghelabeFarhangi MajmaeTashkhiseMaslehateNezam

حداد به مثلث‌های هجومی بسیار علاقمند است. یک مثلث با سه اسم مشخص می‌شود که متعلق به یال‌های‌ آن است. یک مثلث هجومی است اگر اسم هر کدام از اضلاع آن با اسم اضلاع دیگر متفاوت باشد. مثلا مثلث با اضلاع MSN یک مثلث هجومی است ولی مثلث با اضلاع BBC مثلثی است که در عین وابستگی به غرب، غیر هجومی است. حال مزدک تعدادی چوب دارد که اسم هرکدام $F$، $A$ یا $T$ است. به مزدک کمک کنید دریابد آیا می‌تواند با چوب‌هایش مثلثی هجومی بسازد؟ دقت کنید که طول چوب‌ها نیز باید در نامساوی مثلث صدق کند ( یعنی اگر f,a,t طول سه چوب باشند، $f+a>t$ و $f+t>a$ و $a+t>f$)

ورودی🔗

در خط اول $n\leq 10^5$، تعداد چوبها می‌آید. در $n$ خط بعدی در هر خط مشخصات یک چوب می‌آید؛ به این شکل که ابتدا اسم چوب (یکی از حروف $F$، $A$ یا $T$) و سپس طول چوب داده می‌شود. تضمین می‌شود که چوب‌ها به ترتیب طول مرتب شده‌اند و از $10^9$ نابیشتر هستند.

خروجی🔗

در صورتی که یک مثلث هجومی وجود داشته باشد، در خط اول عبارت YES و در سه خط بعد سه چوب را به ترتیب طول چاپ کنید که یک مثلث هجومی تشکیل دهند، به این شکل که در هر خط ابتدا اسم چوب و سپس طول آن چاپ شود. اگر بیش از یک مثلث هجومی وجود داشت یکی را به دلخواه چاپ کنید. اگر هیچ سه چوبی از چوب‌های ورودی یک مثلث هجومی تشکیل نمی‌داد باید عبارت NO را چاپ کنید.

‌مثال🔗

ورودی نمونه 1

5
F 4
A 6
T 11
F 13
F 15

خروجی نمونه 1

YES
A 6
T 11
F 15

ورودی نمونه 2

3
A 1
F 2
T 3

خروجی نمونه 2

NO

ورودی نمونه 3

3
F 1
F 1
F 1

خروجی نمونه 3

NO

عادل به مضارب اعداد علاقه‌ی زیادی دارد. وی فکر می‌کند عددی با مجموعه‌ای از اعداد دیگر اختلاف دارد اگر بر همه‌ی آن‌ها بخش پذیر باشد. وی این اختلاف را جزئی می‌داند اگر عدد مذکور کوچکترین عدد با این خاصیت باشد؛ به بیانی عددی با مجموعه‌ای از اعداد اختلاف جزئی دارد که ک.م.م. آن‌ها باشد.

حال عادل $n$‌ عدد طبیعی دارد. به او کمک کنید ببیند آیا می‌تواند یکی را انتخاب کند که با بقیه اختلافی جزئی داشته باشد؟

ورودی🔗

در خط اول عدد طبیعی $2\leq n\leq 10^5$ یعنی تعداد اعداد عادل می‌شود. در خط بعدی $n$ عدد عادل داده می‌شوند. همه‌ی این اعداد از $10^5$ نابیشترند.

خروجی🔗

در صورتی که یکی از اعداد با بقیه اختلافی جزئی داشت باید "Soal" چاپ کنید. در صورتی که چنین عددی وجود نداشت باید "Tohmat" چاپ کنید.

مثال🔗

ورودی نمونه 1

11
1 2 4 8 16 32 64 128 256 3 768

خروجی نمونه 1

Soal

ورودی نمونه 2

3
1 2 3

خروجی نمونه 1

Tohmat

توضیح🔗

در مثال اول 768 با بقیه‌ اختلافی جزئی دارد.

حداد اخیرا هم‌برگر را کشف کرده و به آن علاقمند شده‌است، اما از آنجا که هم‌برگر کلمه‌ای فارسی نیست به‌جای آن از ترکیب فارسی "نان داغ گوشت داغ" استفاده می‌کند. حال وی می‌خواهد به مناسبت حماسه‌، تعدادی نان داغ گوشت داغ درست کند و به مردم بدهد.

حداد در نان داغ گوشت داغ خود از تعدادی لایه‌ی گوشت، تعدادی لایه‌ی کاهو و تعدادی لایه‌ی سماق استفاده می‌کند. وی تنها همبرگرهایی درست می‌کند که حماسی باشند، یعنی از دستورپخت حماسی وی تبعیت کنند. دستور پخت وی یک رشته از حروف $S$، $B$ و $C$ است که $B$ نشانگر گوشت، $S$ نشانگر کاهو و $C$‌ نشانگر سماق است. وی مطابق با دستور پخت محتویات نان داغ گوشت داغ خود را می‌چیند. برای مثال اگر دستور پخت وی $BSBC$ باشد، ابتدا گوشت، سپس کاهو، سپس یک گوشت دیگر و نهایتا سماق را می‌گذارد.

حال حداد می‌خواهد ببیند چند نان داغ گوشت داغ می‌تواند درست کند. وی در خانه نیز $n_b$ گوشت، $n_s$ کاهو و $n_c$ سماق دارد. همچنین تره‌بار محله‌ی‌شان - وی از تره‌بار نزدیک منزل خرید می‌کند. چرا از جاهای‌گران خرید کند؟ در محله‌ی‌شان قیمت‌ها ثابت است. - این اجناس را به قیمت‌های $B$, $S$ و $C$‌ تومان به ازای هر واحد عرضه می‌کند. وی تنها $m$ ریال تومان پول دارد و می‌خواهد ببیند با اجناسی که در خانه دارد و خریدهای تره‌بارش چند برگر کامل می‌تواند درست کند؟

به حداد کمک کنید.

ورودی🔗

در خط اول ورودی یک رشته‌ی ناتهی از حروف $B$, $S$ و $C$ ‌داده می‌شود. طول این رشته حداکثر صد است. خط دوم شامل سه عدد $n_b$ و $n_s$ و $n_c$ است که تعداد لایه‌های مواد اولیه‌ای را که حداد در خانه‌اش دارد را نمایش می‌دهند. هر سه‌ی این اعداد طبیعی و کوچکتر از صد هستند. خط سوم شامل سه عدد $p_b$ و $p_s$ و $p_c$ قیمت‌های سه جنس است. هر سه‌ی این اعداد طبیعی و کوچکتر از صد هستند. خط چهارم $1\leq t \leq 10^{12}$ مقدار پولی که حداد دارد را نشان می‌دهد.

خروجی🔗

حداکثر تعداد نان‌داغ‌گوشت‌داغ‌های حداد را چاپ کنید. اگر نمی‌تواند هم‌برگری درست کند صفر چاپ کنید.

مثال🔗

ورودی نمونه 1

BBBSSC
6 4 1
1 2 3
4

خروجی نمونه 1

2

ورودی نمونه 2

BCB
1 10 1
1 10 1
21

خروجی نمونه 2

7

عادل به ایجاد رأی‌گیری‌های پرمفهوم و پرمعنا و طرح سوالات چالش برانگیز از مخاطبانش علاقه‌ی خاصی دارد. وی از دوستداران اعداد فارسی است، و این بخاطر علاقه‌ی وی به عادل فردوسی پور است، چرا که فکر می‌کند عادل فردوسی پور فرزند فردوسی است. عدد فارسی عددی است که در آن برای هر دو رقم مجاور، جمعشان بر تفاضلشان بخش پذیر باشد. حال عادل می‌خواهد ببیند آیا این سوال سوالی چالش برانگیز است؟ "تعداد اعداد عادلی که از یک $n$ ثابت کمترند چقدر است؟" اگر حتی شما هم بتوانید این سوال را حل کنید یعنی این سوال بدیهی و غیر چالش برانگیز است. با حل این سوال به شبهه‌ی عادل پاسخ دهید.

ورودی🔗

در خط اول عدد طبیعی $n$ می‌آید. $n$ حداکثر $10^5$ رقم دارد.

خروجی🔗

در تنها خط خروجی باید تعداد اعداد عادل کمتر از $n$ را چاپ کنید. با توجه به این‌که ممکن است تعداد جواب‌ها زیاد شود آن‌را به پیمانه‌ی $10^9+7$ چاپ کنید.

مثال🔗

ورودی نمونه 1

12

خروجی نمونه 1

11

ورودی نمونه 2

15

خروجی نمونه 2

12

توضیح🔗

همه ی اعداد 1 تا 15 به جز 11 و 14 و 15 فارسی هستند.

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

اصغر به اعداد اول علاقه ی عجیبی دارد و به نوعی زندگی خود را مدیون اعداد اول میداند. وی معتقد است علت روی آوردنش به شغل دلاکی و افتتاح بزرگترین حمام عمومی غرب تهران و تبدیل شدن به یکی از ۱۰ مرد ثروتمند تهران همین اعداد اول بوده است.

اما اعداد دیگری هم هستند که اصغر تعلق خاطر بیشتری نسبت به آنها دارد. این اعداد که بعدا به نام اعداد اصغرپسند معروف شدند در واقع اعداد اول را در دل خود دارند!

یک عدد اول اصغر پسند است اگر و فقط به صورت جمع یک عدد با وارونه‌اش قابل بیان باشد. وارونه‌ی یک عدد عددی است که از برعکس نوشتن ارقام آن عدد به دست می آید. مثلا وارونه ی ۳۴۵ عدد ۵۴۳ و وارونه ی ۱۰۰۰ عدد ۱ است.

برای مثال عدد ۱۱ اصغر پسند است زیرا به صورت $10+1=11$ قابل بیان است. برنامه‌ای بنویسید که با گرفتن یک عدد تعداد اعداد اصغر پسند کوچکتر یا مساوی آن را بیابد.

ورودی🔗

یک عدد طبیعی - حداکثر $10^8$ داده می‌شود.

خروجی🔗

تعداد اعداد اصغر پسند کوچکتر یا مساوی ورودی را چاپ کنید.

مثال🔗

ورودی نمونه ۱

4

خروجی نمونه ۱

1

ورودی نمونه ۲

14

خروجی نمونه ۲

2

توضیح🔗

در نمونه‌ی دوم اعداد ۲ و ۱۱ اصغر پسند هستند.

عادل یک گلخانه‌ی $m \times n$ دارد که در $k$ تا از خانه‌های آن کلمات جدید پرورش می‌دهد. اخیرا وی با تکنولوژی جدید گلدان‌هایی یافته که به شکل حروف $L$ انگلیسی هستند و در آن کلمات سریعتر رشد می‌کند. اما چون عادل به حروف فارسی علاقمند است، به جای آن از گلدان‌های تولید داخل ل شکل استفاده می‌کند که دقیقا همان شکل گلدان‌های قبلی هستند ولی فارسی هستند. یک گلدان ل شکل از چهار مربع تشکیل شده و به یکی از ۸ شکل زیر است:

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

ورودی🔗

در خط اول ورودی $1\leq n,m \leq 15$ اندازه‌های جدول داده می‌شوند. در $n$ خط بعدی،‌ در هر خط $m$ کاراکتر '.' یا '#' ظاهر می‌شود که . به معنای خانه‌ی خالی و # به معنای خانه‌ی از قبل پر‌شده است.

خروجی🔗

در تنها خط خروجی باید تعداد راه‌های پرکردن جدول را چاپ کنید. اگر هیچ راهی وجود نداشت صفر چاپ کنید. تضمین می شود تعداد راه های پر کردن جدول کمتر از یک میلیون است !!

مثال🔗

ورودی نمونه 1

3 2
# .
# .
. .

خروجی نمونه 1

1

ورودی نمونه 2

4 4
# # # #
# # # #
. . . .
. . . .

خروجی نمونه 2

2

ورودی نمونه 3

3 3
. . .
. . .
. . .

خروجی نمونه 3

0

توضیح🔗

در مثال سوم از آنجا که ۹ خانه‌ی خالی داریم و هر گلدان ۴ خانه را می‌پوشاند نمی‌توان با گلدان همه‌ی خانه‌ها را پوشاند. در مثال دوم به دو شکل می‌توان با گلدان‌ها جدول را پوشاند:

1 1 1 2
1 2 2 2

و

1 2 2 2
1 1 1 2

کوسه در یک باغ پسته‌ی بزرگ به شکل یک مربع $n\times n$ گیر افتاده است. در این باغ $m$ تمساح حضور دارند. کوسه پس از دیدن عکس زیر، تصمیم گرفته با تمساح‌ها رودررو نشود. کوسه در حال حاضر می‌داند که هر تمساح کجاست. وی همچنین می‌داند که در هر لحظه خودش و تمساح‌ها می‌توانند حداکثر یک واحد به یکی از چهار جهت حرکت کنند یا سر جای خود ثابت بمانند. اما کوسه به دلیل درخت‌های باغ پسته در لحظه‌های بعدی نمی‌تواند موقعیت تمساح‌ها را ببیند. وی همچنین می‌داند که بین بعضی خانه‌های باغ - نه روی حاشیه‌ها - دیوار وجود دارد تا جلوی پسته‌دزدها گرفته شود، و نه کوسه و نه تمساح‌ها نمی‌توانند از دیوارها رد شوند. وی می‌خواهد طوری حرکت کند که هیچ‌گاه امکان نداشته باشد با یک تمساح در یک خانه قرار بگیرد. حال کوسه می‌خواهد طوری حرکت کند که هرطور که تمساح‌ها حرکت کنند وی موفق شود که از جدول خارج شود. اما تمساح‌ها می‌خواهند جلوی وی را بگیرند و ممکن است طوری حرکت کنند که وی موفق نشود، و در این صورت کوسه می‌خواهد مدت زمان بیشتری از رودررو شدن با تمساح‌ها اجتناب کند. به کوسه کمک کنید بداند که آیا موفقیتش تضمینی است یا نه؟ و این‌که اگر موفقیتش تضمینی نیست، حداکثر چقدر زنده خواهد ماند؟

ورودی🔗

در خط اول $n\leq 10^3$ ابعاد جدول و $m\leq n^2$ تعداد تمساح‌ها می‌آید. در خط بعدی $1\leq x,y\leq n$ مختصات کوسه می‌آید. در $m$ خط بعدی مختصات تمساح $i$ام می‌آید. سپس دو جدول $n\times n$ می‌آید. در جدول اول خانه‌ی $i,j$ صفر است اگر دیواری در سمت راست آن وجود داشته باشد و در غیر این صورت یک است. در جدول دوم خانه‌ی $i,j$ صفر است اگر دیواری در سمت بالای آن وجود داشته باشد و در غیر این صورت یک است.

خروجی🔗

اگر کوسه می‌توانست خارج شود باید عبارت "Ma Ahle Koose Nistim" چاپ شود و در غیر این صورت اولین زمانی که مستقل از حرکت کوسه، تمساح‌ها بتوانند طوری حرکت کنند که او را بگیرند را چاپ کنید. تضمین می‌شود که حتما یکی از دو حالت فوق رخ می‌دهد، یعنی ممکن نیست که کوسه نه به تمساح‌ها برسد نه به بیرون زمین.

مثال🔗

ورودی نمونه ۱

3 4
2 2
1 1
1 3
3 1
3 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

خروجی نمونه ۱

2

ورودی نمونه ۲

3 7
2 2
1 1
1 3
2 1
2 3
3 1
3 2
3 3
0 0 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

خروجی نمونه ۲

Ma Ahle Koose Nistim

توضیح🔗

در مثال اول در ثانیه‌ی اول در همه‌ی خانه‌ها به جز خانه‌ی کوسه ممکن است تمساح باشد پس کوسه سر جای خود می‌ماند. در ثانیه‌ی بعدی حضور تمساح در همه‌ی خانه‌ها ممکن است پس در این ثانیه تمساح ها مستقل از حرکت کوسه می‌توانند او را بگیرند.

برای نمونه‌ی دوم به شکل زیر دقت کنید. کوسه در حرکت اول یک واحد و در حرکت دوم یک واحد دیگر به سمت بالا حرکت می‌کند و از جدول خارج می‌شود.

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

سرهنگ علیفر در ترافیک گیر کرده است و بخاطر همین دیر به سرکار می‌رسد تا بازی‌های فوتبال را با لحن جذاب خود گزارش کند.

پس سرهنگ تصمیم گرفته برای کمک به سرهنگ علیفر و همچنین حل معضل ترافیک برای کمک به تبلیغات خود، راهکاری بیندیشد. وی می‌داند تهران $n$ خیابان دارد که $n$ بر سه بخش‌پذیر است و با توجه به تجربیات خود به عنوان یک سرهنگ خبره می‌داند که $\frac{2n}{3}$ تا از این خیابان‌ها دو به دو به یکدیگر متصلند، گرچه دقیقا نمی‌داند این‌ خیابان‌ها کدام خیابان‌ها هستند.

وی تصمیم گرفته تا $\frac{n}{3}$ خیابان را که دو به دو به هم متصلند را یکی کرده و به‌جای آن یک تونل بسازد تا ترافیک را بیشتر کند و سپس با برعکس کردن همین روند، ترافیک را کمتر کند و برای خود تبلیغ کند.

به سرهنگ کمک کنید $\frac{n}{3}$ خیابان پیدا کند که دو به دو به هم متصلند.

ورودی🔗

در خط اول دو عدد $n \leq 2000$ و $m \leq \frac{n*(n-1)}{2}$، به ترتیب تعداد خیابان‌ها و تعداد تقاطع‌های خیابان‌ها آمده‌است. در $m$ خط بعدی، در هر خط دو عدد $1\leq i,j \leq n$ آمده که نمایانگر این است که بین دو خیابان $i$ام و $j$ام تقاطع وجود دارد. تضمین می‌شود $\frac{2n}{3}$ تا از خیابان‌ها هستند که دو‌به‌دو بینشان تقاطع وجود دارد.

خروجی🔗

شما باید $\frac{n}{3}$ خط چاپ کنید که هر خط شامل یک عدد $1\leq j\leq n$ است که نمایانگر شماره‌ی یک خیابان است. این خیابان‌ها باید متمایز باشند و بین هر دوتای این خیابان‌ها باید یک تقاطع یافت شود.

مثال🔗

ورودی نمونه

6 8
1 2
2 3
3 1
1 5
5 3
4 6
2 5
6 3

خروجی نمونه

3
6

توضیح🔗

دقت کنید خیابان‌های 1,2,3,5 به هم متصلند پس $4=\frac{2*6}{3}$ خیابان دوبه‌دو متصل داریم.

غلام به کسرها علاقه‌ی بسیار دارد، و روز و شب به دنبال یافتن معادل فارسی برای کلمه‌ی کسر است. وی واژه‌ی کاملا فارسی تقسیمک را به جای این واژه برگزیده‌است.

اخیرا غلام به نوع خاصی از تقسیمک‌ها به نام تقسیمک‌های سوالی برخورد کرده است. تقسیمک سوالی تقسیمک به شکل $\frac{p}{q}$ است که $p,q$ اعداد طبیعی هستند و $q<p<2q$. ما به این تقسیمک‌ها اعداد گویای بین ۱ و ۲ می‌گوییم ولی لزومی ندارد غلام نیز همین را بگوید، زیرا وی به تغییر دادن کلمه‌ها علاقه‌ی خاصی دارد.

وی همچنین از طریق باجناقش عادل، با تقسیمک‌های تهمتی نیز آشنا شده‌است؛ این تقسیمک‌ها، تقسیمک‌های سوالی‌ای هستند که در‌ آن‌ها $p$ و $q$ هر دو به صورت جمع دو مکعب کامل باشند، به بیان دیگر یک تقسیمک تهمتی به شکل $\frac{a^3+x^3}{c^3+z^3}$ است که $a,x,c,z$ اعداد طبیعی و کوچکتر از $10^9$ هستند. ما به این تقسیمک‌ها چیز خاصی نمی‌گوییم ولی لزومی ندارد که غلام اسمی برای این تقسیمک‌ها ابداع نکند، وی به ابداع کلمه‌های جدید نیز علاقه‌ی خاصی دارد.

حال غلام یک تقسیمک سوالی دارد. تقسیمک سوالی وی را به شکل یک تقسیمک تهمتی بنویسید.

ورودی🔗

در خط اول دو عدد $p\leq 10^8$ و $q\leq 10^8$ به ترتیب می‌آیند که بیانگر تقسیمک سوالی ما هستند.

خروجی🔗

در تنها خط خروجی باید چهار عدد $a$ و $x$ و $c$ و $z$ را به ترتیب چاپ کنید که بیانگر تقسیمک تهمتی باشند. تضمین می‌شود یک تقسیمک تهمتی وجود دارد و اگر بیش از یک جواب وجود داشت یکی را به دلخواه چاپ کنید.

مثال🔗

ورودی نمونه

13 7

خروجی نمونه

4 1 3 2

توضیح🔗

$\frac{13}{7}=\frac{65}{35}=\frac{4^3+1^3}{3^3+2^3}$