$10$ жол мен $9$ бағаннан тұратын шахмат тақтасында «Ци Мэнь Сянци» деп аталатын ойын ойналады. Әр тарапта бірнеше тас бар, ал әртүрлі тастардың сипаттамалары әртүрлі. Біз шахмат тақтасының $x$-ші жолы мен $y$-ші бағанындағы орынды білдіру үшін $(x, y)$ координаталарын қолданамыз.
Біздің тарапта бірнеше Тура (Rooks) мен бірнеше Ат (Knights), сондай-ақ «Кейіп өзгерту» (Shape-shifting) қабілеті бар. Осы екі түрлі тастың жүру әдістері мен қабілеттің сипаттамасы төмендегідей:
- Тура $(a, b)$ координаталарында орналасқан делік. Егер ол бір әрекетте тақтадағы $(c, d)$ координаталарына жылжыса, келесі шарттар орындалуы керек:
- $(c, d)$ орнында өз тастарымыз болмауы тиіс. Яғни ол өз тастарымызды жей алмайды және олармен беттесе алмайды.
- $c = a$ немесе $d = b$, бірақ $(a, b) \neq (c, d)$. Яғни ол өзі тұрған жол немесе баған бойымен қозғала алады, бірақ сол орнында қала алмайды.
- $(a, b)$ мен $(c, d)$ арасында басқа ешқандай тас болмауы тиіс. Яғни ол қозғалу кезінде басқа тастардан аттап өте алмайды.
- Ат $(a, b)$ координаталарында орналасқан делік. Егер ол бір әрекетте тақтадағы $(c, d)$ координаталарына жылжыса, келесі шарттар орындалуы керек:
- $(c, d)$ орнында өз тастарымыз болмауы тиіс. Яғни ол өз тастарымызды жей алмайды және олармен беттесе алмайды.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Мұндағы $\{\dots\}$ реттелмеген жиынды білдіреді. Бұл дәстүрлі шахматтағы «Г» («L») әрпі тәрізді жүріске сәйкес келеді (бұл есепте аттың жолын бөгеу ережесі жоқ екенін ескеріңіз).
- Кейіп өзгерту: Мұны кез келген екі өз тасымыздың орындарын ауыстыру үшін бір әрекет ретінде пайдалануға болады. Қолдану санына шектеу жоқ.
Қарсыласта бірнеше Слайм (Slimes) бар. Слаймдар қозғала алмайды, бірақ келесі сипаттамаларға ие:
- Слайм $(a, b)$ координаталарында орналасқан делік. Оны жеп, тақтадан алып тастаған кезде ол бірден бөлініп, көршілес төрт орынның (жоғары, төмен, сол, оң) әрқайсысында бір Слаймнан пайда етеді. Нақтырақ айтқанда, осы төрт көршілес орынның ішінде бұрыннан басқа тастар тұрған орындарда немесе шахмат тақтасының шегінен тыс жерлерде жаңа слаймдар пайда болмайды.
- Бөліну нәтижесінде пайда болған Слаймдар да дәл сондай бөліну қасиетіне ие және бөліну санына шектеу жоқ.
Тастарды жылжытқаннан кейін, егер олар қарсылас тастарымен беттессе, жеу орындалып, қарсылас тастары тақтадан алынып тасталады. Ойынның жеңіс шарты — қарсыластың барлық Слаймдарын жеп, шахмат тақтасында қарсыластың бірде-бір тасы қалмауын қамтамасыз ету.
Ойын барысында Сяо Бяо қарсылас өз тастарын қозғалта алмаса да, слаймдардың саны көп әрі өте тиімді бөлінетіндіктен, көбінесе одан да көп слаймдар пайда болып, біздің тарапқа оларды таза жою қиын екенін және бұл ойында жеңіске жету мүмкін бе, жоқ па — соны анықтау қиын екенін байқады. Ол стратегия мен талдауға шебер сізге келіп, $10^4$ жүріс ішінде жеңіске жету стратегиясының бар-жоғын анықтауға көмектесуіңізді сұрайды. Егер мұндай жеңіс стратегиясы бар болса, әр қадамдағы амалдарды шығарыңыз.
Кіріс деректер
Кіріс деректер $10$ жолдан тұрады, олардың әрқайсысында шахмат тақтасындағы жағдайды сипаттайтын ұзындығы $9$ жол берілген. Мұндағы . таңбасы бос орынды; C таңбасы біздің Тураны; M таңбасы біздің Атты; ал S таңбасы қарсыластың Слаймын білдіреді.
Әрбір таңба түрі бірнеше рет кездесуі мүмкін. Деректер тақтада кемінде бір Слайм және кемінде бір өз тасымыз бар екеніне кепілдік береді.
Шығыс деректер
Егер $10^4$ жүріс ішінде жеңетін стратегия болмаса:
- Бір жолға
WuJieжолын шығарыңыз.
Егер $10^4$ жүріс ішінде жеңетін стратегия бар болса:
- Алдымен бір жолға
YouJieжолын шығарыңыз. - Келесі жолға әрекеттер санын білдіретін бүтін сан $s$ шығарыңыз.
- Содан кейін әрқайсысында төрт бүтін сан $a, b, c, d$ бар $s$ жол шығарыңыз; бұл қазір $(a, b)$ орнында тұрған өз тасымыздың $(c, d)$ орнына жылжытылатынын білдіреді. Атап айтқанда, егер $(a, b)$ және $(c, d)$ орындарының екеуінде де өз тастарымыз тұрса, бұл әрекет «Кейіп өзгерту» болып саналады және осы екі тастың орын ауыстыратынын білдіреді.
- Сіздің стратегияңыз барлық әрекеттер аяқталғаннан кейін шахмат тақтасында бірде-бір Слайм қалмауын қамтамасыз етуі керек.
Егер бірнеше түрлі дұрыс шешім болса, олардың кез келгенін шығаруға болады.
Формат талаптарына сай келмейтін, тастардың жүру ережелерін бұзатын немесе $(a, b)$ орнында тас жоқ екенін көрсететін шешімдер қате деп есептеледі.
Мысалдар
Кіріс деректер 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Шығыс деректер 1
YouJie 6 1 4 1 3 1 3 1 2 1 2 1 1 1 1 2 4 2 4 1 4 2 7 1 5
Кіріс деректер 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Шығыс деректер 2
WuJie
Ескертпе
$1$-мысалдың шығыс деректері бірнеше дұрыс амалды көрсетеді және соңында барлық слаймдарды жейді.
- $1$-ден $3$-ке дейінгі қадамдар $(1, 4)$ орнындағы Тураның солға қарай бір шаршыдан жылжып, соңында $(1, 1)$ орнына тоқтағанын көрсетеді.
- $4$-қадам $(1, 1)$ орнындағы Тура мен $(2, 4)$ орнындағы Тураның орнын ауыстыратын «Кейіп өзгерту» амалын көрсетеді.
- $5$-қадам $(2, 4)$ орнындағы Тураның жоғарыға $(1, 4)$ орнына жылжығанын көрсетеді.
- Соңғы қадам Аттың $(2, 7)$ орнынан $(1, 5)$ орнына секіріп, жалғыз Слаймды жегенін көрсетеді. Осыдан кейін Слаймға көршілес жарамды бос орындар болмағандықтан, ол бөліне алмайды. Ойын жеңіспен аяқталады.