D. Шрек Илжиг 2-т тусална уу 2

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өмнөх раундаас хөзрийн тоглоомыг оновчтой байдлаар тоглож сурсан(мэдээж хэрэг Codeforces-ын тэмцээний оролцогчид байхгүй байсан бол сурахгүй байсан) Шрек болон Илжиг нар(таны мэдэж байгаачлан тэд ч бас Холын холын хаант улсад амьдардаг) уг уйтгартай тоглоомоос гарч тоглоомон цэргийн тоглоомыг тоглохоор болжээ.

Тоглоомын дүрэм дараах байдалтай байна: нэгэн тулааны талбар өгөгдөх ба уг хүснэгт нь $n × m$ ширхэг квадрат агуулж байх бөгөөд зарим нүднүүд дээр тоглоомон цэргүүд (ногоон цэргүүд нь Шрек-ийн цэргүүд ба улаан цэргүүд нь Илжигний цэргүүд байна) оршин байх юм. Түүнчлэн талбарын $n$ ширхэг мөрийн мөр болгонд 2-аас ихгүй тооны цэрэг өгөгдсөн байна. Ээлж бүрд тоглогчид өөрт харьяалагдах $1$-ээс багагүй $k$-ээс ихгүй тооны цэргийг сонгох бөгөөд тэдгээр цэргүүддээ довтлох эсвэл ухрах тушаал өгөх юм.

Довтлох гэдэг нь бүх сонгогдсон цэргүүдийн хувьд хийгдэх үйлдэл бөгөөд хэрэв тэдгээрийн оршин байгаа мөрүүд дээр дайсны цэрэг оршин байвал тухайн мөрийнхөө дагуу дайсны цэрэг уруу чиглэн хөдлөх үйлдэл юм. Хэрэв сонгогдсон ямар нэгэн цэргийн оршин байгаа мөр дээр дайсны цэрэг оршин байхгүй байвал уг сонгогдсон цэрэг нь тоглогчийн энэ үйлдлийн туршид ямар ч чиглэл уруу хөдөлж болох юм. Сонгогдсон цэрэг болгон нь дор хаяж нэг нүдээр хөдлөх ёстой. Мөн ялгаатай цэргүүд нь ялгаатай тооны нүдээр хөдөлсөн байж болно. Довтлох үеэр цэргүүд нь өөр цэрэг оршин байгаа нүдийг өнгөрөн явж болохгүй бөгөөд оронд нь шуудхан зогсох юм. Өөрөөр хэлбэл бусад цэргийг өнгөрөн явахгүйгээр өмнөх нүдэн дээр нь зогсоно. Мөн тулааны талбараас гаран явж болохгүй бөгөөд өмнө дурдсаны дагуу аливаа довтолж буй цэрэг нь довтолгоогоо өөр цэрэг зогсож буй нүдэн дээр дуусгаж болохгүй юм.

Ухрах гэдэг нь бүх сонгогдсон цэргүүдийн хувьд хийгдэх үйлдэл бөгөөд хэрэв тэдгээрийн оршин байгаа мөрүүд дээр дайсны цэрэг оршин байвал тухайн мөрийнхөө дагуу дайсны цэргийн эсрэг чиглэл уруу хөдлөх үйлдэл юм. Уг үйлдлийн бусад дүрмүүд нь довтлох үйлдэлтэй ижил байна.

Жишээлбэл анхны тулааны талбарыг дараах байдалтай байна гэж үзье. Энд "G" тэмдэгт нь Шрек-ийн ногоон цэргүүдийг илэрхийлэх ба "R" тэмдэгт нь Илжигний улаан цэргүүдийг илэрхийлнэ:

-G-R-  
-R-G-

$k = 2$ бөгөөд Шрек эхний үйлдлийг хийнэ гэж үзье. Хэрэв тэрээр довтлох тушаал өгвөл түүний уг үйлдлийн дараа тулааны талбар нь дараах байдалтай байж болох юм:

--GR-     --GR-     -G-R-  
-RG--     -R-G-     -RG--

Хэрэв өмнөх тохиолдолд Шрек ухрах тушаал өгсөн бол түүний уг үйлдлийн дараа тулааны талбар нь дараах байдалтай байж болох юм:

G--R-     G--R-     -G-R-  
-R--G     -R-G-     -R--G

Өөр нэг талаас харвал Шрек өөрийн үйлдлээ зөв хийсэн тохиолдолд дараах тулааны талбаруудыг гаргах боломжгүй байна:

G--R-     ---RG     --GR-  
-RG--     -R-G-     GR---

Шрек тоглоомыг эхлүүлнэ. Үйлдэл хийх гэдэг нь дүрэм ёсоор довтлох эсвэл ухрах тушаалуудын нэг нь байх юм. Нүүдэл хийж чадахгүй болсон тоглогч ялагдах бөгөөд түүний өрсөлдөгч нь тоглоом ялна. Тэгвэл тоглоомын ялагчийг тодорхойлж өгнө үү. Түүнчлэн тэд үргэлж ухаалаг байдлаар тоглох бөгөөд тодруулбал хэрэв тэд боломжтой байвал хожих гэж эсвэл тэнцэх гэж оролдох ба хэрэв тэд хожиж чадахгүй байвал тоглоомыг аль болох удаан үргэлжлүүлэхийг хүсэх юм.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $n$, $m$ болон $k$ ($1 ≤ n, m, k ≤ 100$) өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг тэмдэгт өгөгдөнө. Эдгээр тэмдэгтүүд нь бүгд {"-", "G", "R"} гэсэн олонлогт харьяалагдах бөгөөд уг олонлогийн элементүүд нь харгалзан тулааны талбарын хоосон нүд, Шрек-ийн цэргийн байрлаж буй нүд болон Илжигний цэргийн байрлаж буй нүдийг тус тус илэрхийлнэ.

Мөн мөр болгонд 2-оос ихгүй тооны цэрэг оршин байх юм.

Гаралт

Хэрэв өгөгдсөн тоглоомон цэргийн тоглоомд Шрек ялах бол "First" (хашилтгүйгээр) гэж хэвлэнэ үү. Хэрэв Илжиг ялах бол "Second" (хашилтгүйгээр) гэж хэвлэнэ үү. Хэрэв тоглоом хязгааргүй хугацааны турш үргэлжлэх бол "Draw" (мөн хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2 3 1
R-G
RG-
Гаралт
First
Оролт
3 3 2
G-R
R-G
G-R
Гаралт
Second
Оролт
2 3 1
-R-
-G-
Гаралт
Draw
Оролт
2 5 2
-G-R-
-R-G-
Гаралт
First
Сэтгэгдлүүдийг ачааллаж байна...