Независимо дали на компютър, Gameboy, или на старата си Nokia, най-вероятно всеки от вас все някога е попадал на играта Snake.

Замисляли ли сте се някога да напишете изкуствен интелект, който я играе? Защото някои хора са. Ние, обаче, ще пробваме да направим дори по-умен такъв!

Ще разгледаме малко по-разчупен вариант на играта, в който двама играчи играят на една и съща дъска с N реда и M колони, борейки се да изядат първи K ябълки. Стандартните правила важат, с няколко допълнения, за да се отчете втория играч:

1. В началото на играта змиите са с дължина 1.
2. Изяждането на ябълка прави змията ви с един сегмент по-дълга.
3. Опит да се премине през поле, в което има част от змия (независимо дали вашата собствена или тази на противника) е невалиден ход и губите моментално.
4. Опит да се излезе извън дъската е невалиден ход и губите моментално.
5. Ябълките се генерират на случаен принцип в полета, в които няма част от змия.
6. В момента, в който някоя от змиите стане с дължина K+1 (след изяждането на K ябълки от съответния играч), играта свършва моментално и той е обявен за победител.
7. Ако 2 * (N + M) хода никоя от змиите не изяде ябълка, играта свършва и печели по-дългата от тях. Ако са с равна дължина, печели тази, която последна е изяла ябълка. Ако никоя от змиите не е изяла ябълка, печели първият играч.

• Стъпването върху полето, където вашата змия свършва, не е позволено (тоест първо се движи главата, а после остатъка от тялото).
• Когато змия изяде ябълка, тя расте откъм главата си. По-конкретно, главата на змията застава върху ябълката, а досегашното ѝ тяло не помръдва.
• Позициите на ябълките са предварително генерирани на случаен принцип и се ползват една след друга. В случай, че на някоя позиция има тяло на змия, тя се пропуска, и се пробва следващата (докато се стигне до позиция, която е свободна).
• За да е честно, всяка дъска (с една и съща дъска и генериране на ябълки) се играе по два пъти - веднъж вие като първи играч и веднъж противникът ви като първи играч.
• Изкуственият ви интелект трябва да не мисли повече от 0.2 секунди на ход.

Ще наречем играта "Two snakes, one apple", или накратко - Snakes. На първия ред на стандартния вход ще бъдат зададени три цели числа N, M и K - съответно броя редове и колони на дъската, следвани от броя ябълки, които трябва да изяде вашата змия, за да спечелите. Следват N реда, всеки съдържащ по M символа. Символ '.' обозначава празно поле. Символ '@' обозначава ябълка. Главна буква от английската азбука ('A'-'Z') обозначава част от вашата змия, като буквата 'A' е главата ѝ, 'B' е частта от тялото точно след главата ѝ, и така нататък. Малка буква от английската азбука ('a'-'z') обозначава част от змията на противника ви, описана по сходен начин. На стандартния изход изведете посоката, в която искате главата на змията ви да се премести на следващия ход: "Up" за нагоре, "Down" за надолу, "Left" за наляво, или "Right" за надясно.

• 5 ≤ N, M ≤ 20
• 3 ≤ K ≤ 10

Примерен Вход	Примерен Изход
7 14 10 cdefghij...... ba............ .........@.... .............. ....BA........ ....C......... ..FED.........	Up