using System;

using System.Collections.Generic;

​

class Program

{

    static void Main(string[] args)

    {

        // Заданный лабиринт в виде строки

        string input = @"1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

001000000000001000001010000000000010000000000000000000000010000000001000000000001000000000100000100000000010000000000010000000100000000000100000000000000000100000001000100000000010000000000000100000001

101111111011101110101010101011111110111111101111111111111010111111111011111110101110111110101110101111111010111011111110101011101110111110101111111110111110111011101010111011111011111010111111101111101

100010000010100010101000101010000010100010001000100000001010000000000000000010100010100010101000001000000010101000001000101010001000100010100010000010100010000010000010000010001000001010001000100000101

111010111110111010101111101110111010111010111011101010111010111111111011111010111010101110101111111010111110101111101011101110111011101011111010111010101011111110111111110110101111101110101010111011101

100010100000101010100010001000100010000010001000001010100010001000001010001010101000101000100000000010001000100000101010001000101000101000001000100010001010001000100010000010100000100010100010100010001

101110101110101010111010111011101110111111101011111011101111101011101110101110101111101011101111111111101011111011101010111011101110101110101111101111111010101011101010111110111110111010111110101110101

101000101010001000100010001000100000100000001010000010001000001010100000101000100000001010101010001000101000000010001010000010000010001010101000001000001010100000101010100000100010001010100010001000101

101011101011101111101110101110111111101111111110111010111111111010111111101011111110111010101010101010101011111110111011111110111011111010101011111011101011111111101010101111101010101010111011111011101

101000101000100000101000100010000000100000100000100010000000000010000010101010000010001010101010100010101010000000100010000010100000000010101000100010001010000000001010001000001010101010000010000010001

101110101110111011101011101111101111111110101011111111111111111111101010101010111011101010101010111110101010111111101111101010111111111010111110101110111010111111111010111011111010111011111010101111101

100010100010000010001000100000101000100000101000000000000010000000001000100010100000001010001010001000100010000000100000001010100000001010100000001000001010100000100010100010001010000000001010100000101

111010101011111110111110111110101010101111101111111111101010101111111111111110111111101010111011101110101111111010111111111010101111101010101111011111111010101110101110101110101011111111101010111010111

101000101010000000100000100010101010001000100010000000001010101000001000100000001000001010001000100010100010001010000010000010000010001010101000100000001010101000101000100010101000000000101010000010001

101111111010111111111110111000101011111011111010111111111010101011101010101111101011111011101010111010111110101110111010111111111110111110101011101111101010101111101111111010101111111110101111111011101

100000001010000000000010000010001000100010001010000000100010100010101010001010001010000010000010100010000000101000100010100000000000100000101000101000000010100000100000000010101000001000100010001010001

101111101011111111111011111111111010101110101011111110101110111110101011111010111110111110111111101111111111101010111110101111111110101110101010101111111110111110111111111110101110111011111010101110111

100010000000100010000010000010001010100000101000001000100010100000101000100010000010100000100000101000100000101010100000101010001000100010101010100000000000000010000000000000100000100010100010100010001

101011111110111010111010111010101010101111101111101011111010101110101110111011111010111111101110101110101110101010101111101010101011111010101110111111111111111010111011111111101111101110101110111011101

101000000010000010100010101000101010101000100000001000100010101000100010001000101010000000001000100010101010001010100010001010100010001010100010000000001000001010100010000000101000001000101000101010001

111111111011111010101010101111101110101010111111111110111110111011101111101010101011111111111011101010101011111010111010111010111110111011111010111110101011101010101110111110111011111110101011101010101

100000000010001010101000100000100000100010101000100010100000100010001000101010101000000000001000101010101000000010001010001000100000001000100010001000101010101000100010100010100010001000100010001000101

101111111110101010101111101111111111111110101010101010101111101010111010101010101111111011111110101010101111101111111011101011111111101110101111111011111010101111101110111010101110101011111110111111101

100000100000100010001000100000000000000010001010001000100010001010100010100010001000001010000000101010000000101000000010001010000010001010000000000010000010000000101000100010100010100010000000100000101

101110111010111111111010111011111110111011101011111111111010111010101110111111101010111010111111101011111110101011111110111010111010101011111111111010111011111110111011101010111010111110101110101110101

100010001000001000100010001010000010001010001000000010001010001010001010000000001010001000100000101000000010001000100010001000101000101010000010000010101010000010000010001010100010000000101000101010101

101111101111101010111011101110111011110010111111111010101011101011111011111111111011101111111010101111111011111110101010101111101111101010111011111110101010111011111110111110101110111111101111101010101

101000001000000010001010100000101010000010000000101000101000101000100010001000001000100000000010100010100010000000101010100010000000000010100010000000101010101010001000000010001010000000100000101010001

101011111011111111101010111111101010111111111110101111101110101110101010101110101111101011101111111010101010111111101010111011111011111110101110101111101010101010111011111011111011111110111110101011111

101010000000100010000010000000101000100000000010000000101000100010001000100000100000101000101000001010101010001000000010001000001000100000000000100000100010001010001000101000100000001000100010001000001

101011111111101011111111111010101110101011101111111011101011111011111011111011111110111110101011101010101111101011111011101111101111101111111*11101110101111101010101110101110101011101011101011111011101

101000001000101000101000000010100010101010101000000010001010000010000010001000100010000010000010001010100000101010001000001000101000100000101010001000101000001010101000100010001010001000001010000010001

101111101010101110101000111110101110101010101011111110111010101110111110101010101111111011111010111010111011101010101111101110101010111110101010111011101011111011101011101011111011111111111010111111101

10100000101000100010001010001010100010101000101000*010000010101000001000100010100000101000001010001000101000001000101000100000100010000010101010100010101000001000100010001000100010000000101010100000101

111011111011111011101110111010101011101011111011111011111111101111111011111110101010101111101111101110101111111111101010111110111111111010101010101110101111101110101111111011101010111010101010101110101

10001000001000100010001*001010101000101000001010001000000000100000000010000010101010000000100000100010001000000000101010000000000010000010101010100010001000100010101000001010*01010101010001010100010101

101110111110111110111111101010101110101111101010101011111110101111111110111010101010111111111110101111101110111110101011101111111010111010101010111011101011111010101011101010111110101011101010101110101

100000100000000010000010001000001000101010001000101010001000100010000010100010101010100010000010100000100000100010101010100000001010101010100010101000100010001010100010000010000000101010001010101000101

101111101111111011111010111011111011101010111111101010101011101110111010101110111001101010111010111110111111101010111010111111101110101010111110101110111110101010111011111111101111101011111010101011101

101000100000001000001010001010000010001010000000001010101010001000100010101000001000001000001010100000000000001010100010000000100000100010000000000010000000100010001010001000100000001000100010001010001

101010111110111110101010101110111110111011111111111010101011101011101110101011101111111111111010101111111111111010101111111011111111101111111111111111111111111111101010101010111111111110101111111010111

10101000000010000010101010100010100010100010000000001010000010001010100010101000100000001000001010000010000000001000100000101000000000100000001000000000000010000000101010001000000010*010000010000010001

101011111110101111101010101011101011101010101011101111111110111010101110101010101011111010101110101110111111111111111011101010111111111110111010111111111110101111111010111111111110101011111010111111101

101000100010100010001010100010001010001010001010001000000010100010100010101010101000101010101000101010001000100000100000100010100000000000101010100000000010100000001010000010100010001000100000100010001

101110101010111010111011111010111010111011111011111011111010101110111010101110111110101010111011101011101010101010111110111010111011111111101010111110111110111011101111111010101011011110011111101010111

101000101010100010100010001000100010000010001000001000100010001000001000100010000000001010001010000000100010001010000000101010100010000000000010000010000010001000100000001010001000000010001000101000101

101111101011101110101110101110101110111111101111101110001111111010111011111011111111101010101011110110111111111011111111101010101111111111111011111010111011101111111011111011111111111011101011101111101

100000101010001000100000100010101000100000001000101000100010000010000010001000000000101010101010000010100000101010001000100010100000100010001010001010001000101000001000001010000010000010001000100010001

111110101010111111111111111011101011101110101010101011111010111111111110101111111110101010101010111010101110101011101010101110111110101010101110101011101110101011101111101010111010111110111110111010111

100010101010100000000010001010001000100010101010001010001010100000001000100000000010101010100010100010101000001000100010001010100010101000101000101000100010101000100000001000100010100010100010001010001

101010101010101111111010101010111110111010101010111010101011101111101011111111111010100010111110101110101011111110111011111010101010101111101011101110111010101110111111111111101110101010101010101011101

101010001010100000100000100010001000100010101010100010101000001010001010001000000010101010001000100010001010000010001000000010001010100000101000100010001010000000100000100000100000101000101000101000001

101111111010111110111110111111101110111110101010101111101111111010111010101011111110101011101011111011111110111010101111111011111010111110101110111011101110111110101110101110111110101111101111101111101

101000000010001010000010100000100010000000101010101000000010000010000010100010001000101000100010001000000000100010101000100010001010000000100010101000101000001000100010000010001000101000000010001000001

101011111110101011111011101110111011111111101011101011111010111011111110111110111011101110111111101111111111101111101010101111101011111011101110101110101011101011111011111111101011101110111011101011111

1010100000001000100010000010100010001010000010001010100010001010000000101000001000100010001000001000000000101000001010101000000010000010001010001000101*1010001000100010001000101000100010001000101000101

101010111110111010101111111011101110101011111110101010111111101011111110101110101111111011101110111011111010111110101010111111111111101110101011101110101010111011101111101010101011111011101110101110101

101010100010101000101000100010100000100000000010100010100000000010000000100010100000100010000010000010001000000000100010000000100000100010101010100000100010100010001000001010100010001000101000100010001

101010101110101111101010101010111111111111111110111110101011111110111111101010111110101111111011111110101110101111101111111110101010111010101010101111111110101110111011101010111110101110101011101111101

101010001000100000100010001000100000001000000000100010000010000010000010101010000010001000000010000010100010101000001000100010001010100010101010000000000000100010000010001010100000100000101010001000001

101011101011101111111111111100111011101011111110101010111110111011111010101011101111111011111110111110111010101110111110101010111011101111101011111111111110111111111110111010101111111111111010111011111

101010001000100000100000000010001000100010000010101000100010001000100010001000101000000010000010000010101000100010000000101010101000001000001000001010000010100000001000100010101000001000000010100010001

101011111110111110101111111011101110111110111011101111101011101110101111111110101011111010101011111010101111111011111111101010101111111011111111101010101110101010111011101110101111101011101011101110111

100010000000100010100000100010100010000010001000001000101000001000101000000010101010000010101000000010000000101010000010001010100000001010000000101000100000101010100010101000100000100010001010001000001

101110111111101010111110101010111010111011101111111110101111111011101011111010101010111110101111111011111110101010011010111010111110101010101110101011111111101011101110101011111110111110101110111111101

101000001010001000001010101000001010001000001000000000100000101000101000001010101010100000100000001010000000101000101000100010000000101000101000101000000000101000100000101000000000100000101000100000001

101111101010101111101010101111111011111011111111101011111110101110001011111010101010111111111110101010111111101111101111101111111111101111101111101111111110101110101111101101111111101011111011101111101

100010001010100010000010100000001000001010100000101010000000100010100010000010101010000000000010101010101000001000000000100000100000100000100000100010100010100010001000001000100000001010000010100000101

111010111010111011111110111111101111101010101010111010111111101010111010111110111011111111111010101010101010101110101011111110111011111110111110111010101010111011111010111010111011101010111110101110111

10101000101000101000100010001000100000101000101000001010100000101000101010000000001000000000101010101010001010001010101000100010001000001000100010001000100*001000001010100010001000101010000010000010001

101011101011101010101011101010111011111011111011111110101011111011101110101111111111111111101011101110111110111011101010101011101110111011101010101110111111111111101010101111101110101111111011111011101

101010001000001000100010001010001010000010001000100000101000001000100000100000000000000000001000100000000000101000101010100010100000001000100010101010101000000000101010101000100010100000001000001010001

101010111111111111111010101111101011111010101110101111101110101110111111111111111101111111101110101111111111101110101110111110101111111011111110101010101011111110101010101110111011101111101111101010101

101010100000100000001000101000101000001000100000101010000000101000100000100010000010000000100010100010000010000010100010001000000010001000100000101000001010100010001010100010001000100000100000101010101

101010101110101111101111101010101111101111101111101010101111101010101010101010101010111011101110111110011010111010111011101011111110101110101110101111101010101011110010111011101110111110100011101010101

100010100010101000101000001010000000100000101000001000100000101010101010101010101010001000101000100000100010100010001000101000001000100010001000100000101010001010001*10001000000010100010101010001010101

101110111010101010101111111011111110111110111011011011111110101010111010101010101111101110101011101111101110101111101011101111101011111010111010111010111011111010101011111011111110101010101110111110101

1010000000100000101000000010100000100000100010001000000000100010100000101010101000001010001010000000100*1000100000001010001010001010001010101010001010100010001000101000000010000000101000100010000010101

101011111111111011111111101010111011111111101010101111111111111011111110111010111110101011101111111110111011111111101010111010111011101010101001101110101110101111101111111010111111101111111011111010101

101010000010001010000000001000101000000000101010101000000010000010001000100010001010101000001010000000100010001000100010001000001000100010001000100010101000100000001000001000100000101010000000100010101

101011101010101110111111111011101111111110101010101010111010111110111011101011101010101111111010111111101110111010111111101110111110101111111110111010101011101111101011101011101111101010111011101110111

10100000101010000010000000101000000010001010101010101000100010001000001000101000001010000010001010001000100010001000000*100010100000100000100010001000101010101000101000101010000000000010100010001000001

101111110110111111111011111010111110101010101110101011101011101010111110111010111110111110101110101010111110101111111110111011101111111110101011101111101010101010101110111010111111111110111110111111101

101000000010001000001000100*10100000101000100000101000101010001010000000100010001000100000101000101000000010101000000010001000101000000010001000100000000010001010101000100010100000001000100000100000001

101011111011101110101110101111101011101111111111101110101110101011111111101110111010101111101010111111111010101110111010101110101011101011111110101111111111111010101010101110111111101011101111101111101

100010001010001000100000101000001010001000000000101000100000101010001000101010100010100010001010100010001000100010001010100010001000101010000010100000100010000010100010101000100000101010001000001000101

111110101010111011111110101110111010111011101110101011111110101010101010101010101110111010111011101010101011111011101010111011111111101110111010111110101010111110111110101110101110101010111010111110101

100000101000100010000010100000100010100010001000101010000010101000101010101010100010001010001000001000101010000010001010001000000000001000100010001010101010100010100010100010001000001000100010100010001

101111101111101110111011111111101110101110111111101010111010101111101010101010111011111010101111111111101110111110111111101110111111111011101111101010101010101010101010111011111011111011111010101011101

10100010000000100*101000000000100010001010001000100010001010101000101010000010101000000010100000100000100000000010100000101000100000000010100000101000101000101010001010001010000010001000001010101000101

10111011101011101110111111111011101111101110101011101110101010101010111111101010111111111111101010111011111111101010111010111110111111111*111110101011101111101111111010111010111110101111101011101110111

100010001010100010001000100010001010001000100010001000101010001010001000001010100000000000001010001010001000100000101000101000001000000000001010001000101000100000001010100010100010100010100010001010001

111011101011101110101010101010111010101110111111101011101011101011101011101010111111111011101011111011101010111111101110101011111001111011101011111110101010101110111010100011101010111010111010111011101

101010001010001000100010001010001010100000001000101010001010001010001010001010000000100010101010000010001010000000100010001000100010001000101000100010101010001000100010101010001010101010001010100000101

101010101010111110101111111011101010111111101010101010111011111011111010111111111110101110101011101010111011111110111011101110111110101110101010101011101011111011101111101110111010101010101010111110101

101010101000000000101000001010001010000010101010100010001000001000100010100000000010100010101000101010101010000010001010000010000010100000101010001000001010001000101000100010001010101010100010000010101

101010111111111111101011101110111011111010101010111111101111101110101110101111111010101010101110101010101010111111101011111011111010111111101011111111111110101010101010111011101010101010111111111010101

101010100000000010001000100000100000000010000010001000001000100010000010000010001000101010000000101000001010000010001000001000100010001010001000000000100000101010000010000010001000001010100000001010101

101010101111111010111110111111101111111111111111101011111010111011110111111011101111101011111110111111111011111010111111101111101111101010111111101110101111101110111111111110111111111010111011111010101

101010101000001010000010100000100010000000000000101000100010001000100000001000100010001000100010100000001000001010100000001000001000001010000000100010100000100010001000100000101000100010000010000000101

101010101010111010111110101110111010111111111110111010101111101110101111101110101010111110101011101111101011101010101111111011111011111011111110111010111011111011111010101111101010101111111010111111101

10000010101010001010000010001000001000100000001000101010100010001000101000100010101010000010100000100010100010101010000000100000001000100010000010001000001000100000001000100010101010100000001*101000001

101111101011101110101111111011111111101011111011101110101011111011111010111011101011101111101011111011101111101010111111101111111110101110101111111011111110101110111111111010101010101111111010101011111

100010001000001010101000001010001000101000001000100000101010000010000000101000101000100010001010001000000000001000000000100000000000100000101000001000100010100010000000000010100010100000001010001000001

111010111011111010101010111010101010101111101010111111101010111110111111101110101110111010111110101011111111111111111110111010101111101111101011101111101010101011111111111110111010111111101110111110101

101010100010000000100010001000101010100010001010100000001010100010100000101000101000100010001000101000100010001000000010000000101000101000001000100000001010001000100000100010001010001000100000100010101

101010111011111011111111101111101010111010111010101110111010101110111010101011101110101011101011101111101010101011111011111011111010101010111110111111111011101110101110101011101110101110111111101011101

100010001010001000001000100000000010001010100010101010001000100010000010101000100010001000100000100000101010100010001010000010000010101000100010100000001000100010100010001000100010100000001010001000001

111111101010101110111010111110111111111010101111101011101011111011111110101110111011101111111110111110101010111110101011111110111110111110101010100111111110111010111011111110111010111111101010111111101

100000001000101000100010000010100000100010100010001000101000001000100000100010001000101000001010100010001000100000100010000000100010001000101000101000000010001010000010000010101010001000001010000000101

101111111111101011101111111011101110101110111010111110101111101011101111101011101010101011101010111011111111101110111110111111101111101011101111101011111011101011111110101110101011101011111011111110101

100000000010101010001000000000001010001010001010001000100000101000100010001000001010101000101000001000100010001000100010100010000010001010001000000000001000100010100000100000100000001000000000000010101

101111111010101110101111111111111011111011101011101011111110101110101010111111111010101110101111101011101010111011101010101110111010101001101110111111111010111110101111111111101111111111101110111110101

101010000010100010101000000010000010001000001000101000100000100000101010000000100010101010100010000010001000100010001000101000100010101000100010000010000010001000101000000010001000000000100010100000101

101010111110111010111010111010101010101011111110101110101111111110101011111110111110101010111011111010111111101110111111101011101110111110110011111110111111101110101011111010111011111110101011101111101

101010000010001010000000100010101000101000001010001000101000100000101000100000001000101010001000101010000010001010001000000010001000100010001010000010100000100000100010100010001000100010001000001000001

101011111011101011111111101111101110111111101001111011101011101111101110111111101011101011101110101011111011101011101111111110101010101011101010111010101110111111111110101111101110101011111111111011111

101000001000100000001000001000101000100000100000000010001000101000000010000000101010000000100010100010001000101000101000000010101010101000100010100000101000100000000000101010000010101000000010001000101

101011101110111111101011111010101011101011111111111010111110101011111011111100101010111111111010001111101110101110101011111010101010101010111110111111101010101111101011000010111110101111111011101110101

101000100010000010000010000010101010001000000000101010100010000010001010001000100010001000000010100000000010100000101000001010101010101010100000000000001010101000101010001000100000100000001000100010101

101110111011111011111110101110101110111111111010101010101011111110101010111011111111111011111110111111101110111111101110101010101011101011101111111111111010101010101010111011101111101111101110111010101

101000001000001000001000101000100010001000100010001010001000001000101010100010000010001000000010001000001000100000001000101010101000001010001000000000100010100010101010001010001000000000100010000010101

101111111011101111101010101011111011101011101110111011111111101011111010000111101010101111111011101011111010101111111011101010101111111010111111101110101110111011101011101110111111111110111011111110101

100010000010101000100010101000001000101000100010100010000000101000000010101000001010100000000010001010000010100000100010100010101000101010001000101010101000100010001010100010100000100000001000100000101

111010111110101010111010101111101110101110111010101111101110101011111110101010111010111110111110111110111110111110101110101110101010101011101010101010101111101110111010111010101110111111111110101111101

101000100010100010100010101000100000100000001010100000101000101010000000101010101010001000001010100000100000000010001000101000100010001000100010001000100000100010001000100010101000000000000010100010001

101111101010111011101110101010111110111111101011111110101011101010111110101110101011101011101010111011111111111011111010101011111111101011111111111011111110111011101110101110101111111111111010111011101

100000001010001010001000101010100010000000101000001000101000101010100000101000101000101000100010001000000000100000000010101000100010101000100000101010100010001010001000100000100010001000001000001000101

101111101011101010111011001011101011111011101111101011111110101010101111101011101110101010101111101111101110111111111110101110101010101110101010101010101011101010111110111111101010101110111111101110101

101000001000101010001000101010001000000010000010001000001000101000101000100010000010001010101000001000101010001000100010100010001010000000001010001010001000100010100010100000101000100010000000001000101

101011111110101011101110101010111111111110111110111111101010101111101011111110101111111110101011111010101011101011101010111011111011111011111011111011111110111110101010101110101111111011111111111011101

101000001000001010101010001000100000100000101000100000001010100010001000100010101000000000101000001010100010001000001000101000001000100000100010001000100000000010001010001000100010001000100000001010001

101111101011001010101010101110101110101111101011101111111010111010111010101010101011101111101110101010101110111111111011101111101110101111101110101110101111111011111011111011111010101110101111101011101

101000101010001010101010100010001010100000001000000000000010001010001010101000101000100010001000101010101000100000001000001000100000101010001000100010101000001000100010000010100010100010001000100010001

101110101010111010101010111011111010111111101111111111111111101011101110101111101110111010111110101010111011101111101111101110111111101010101011101010101010111110101110101010101110101011111110111110101

100000101010100010101000101010000010101000001010000010000010100000100010100000100000101010000000100010001010001000100000100000000010000010101010001010001010100010101010100010101000101000100010001000101

111110101010101110101011101011111010101011111010111010101010101110111010111110111111101011111111111111101010111011111110111111101110111110111010111111111010101010101010111110101011101110101010111010111

100010101010101000101000001010000010101010000010001010101000101010001000000010001000001000000010000010001010100010000000101000001000101000100010100000001010101010101*00000000101010001010001010000010001

101010101010101110101111111010111010101011101011101010101111101011101111111011101110111111111010111010111010101110111111101011111011101010101100101110111010101010101011111111101010111011111010111111101

101010101010100010101000001010001010101000001010001010100000101000101010000000100010000000001010001000100000001000100000100000001000101010100010101010000010101010101010000010001010100000001010001000101

101010101010111010101011101011101110101111111010111010111110101011101010111111111011101010111011101111101111111011101110101111101110101010110010101011111110101010101110111010111110111110111011101011101

101010001010*01000101000101000100000001000001010100010000010101010001010001000001000001010001000101000000010000010000010101000100010101010100010100000100000101010100000001010100010000010001010001000101

101010101010101110101110101010111111101010111010111011111010101010111010111010111111111011101100101011111110111111111010101010111110101011101110101111101111101010111111111010101011111011101010111110101

101010101000101000100000101010100010101010100010001000001010100010001000100010000000000010001010001010000010100000000010101010000010001010001010001000001000101000100000100010001000000010001010100000101

101010101111101011111111101110001010101010101101101111101110111011101011101111111111111110101011111110111010101111111110101011111011101010111011111011111010101111111010101111111111111110111010101111101

101010100000101010000010001000101010001010101000101000100010000010001000101000000000100000100010001000101000101000000000100000001000001000100000001000100010101000000010100000100010000010001010001000001

101010111110111011111010111011101011111010101011101011111011111110111011101011111010101110111010101011101111101011111111101111101111111010111110111110101110101011111110111110101010101010101011101011101

101010101000100000000010001000001000100010001000101000001010000000100010001000100010100010001000100010000000001010100000000000100010000010000010000010001010001010001000100000101010101010100010001010001

101110101011101111111011101111101110101111111110101110111010111111101110111111101110111011101111111111111011101010101111111111101110101011111010111011111011111010111011101110101010101110111011111010111

100010101000001010001000100000100010100010000000100010001010100000100010000010001000100000101000000010001000101000101010000000001000100000001010001000100000100010001010001000101000100010100000000010001

111010101111111010101111111110101110111011101110111010101010111011111011111010111011101111101011111010101110101111101010111111111011111111101011111011101011101011101010111111101111111010111011111111101

100010001000000010101000100000100000101000001000001010100000100010000010001010101010001000101010001000100010100000001010000010001000001000101000001000001010001010001010001000101000001000100010000000101

101111101111101010101010101111101010101111101111111011111111101010111110101010101011111010101010101111111010111111101011111011101111101110101111101111101010111010111011101010101010111111101111111110101

101000101000101010101010001000101010001000001000000010000000100000100000100010101000000010101010100000001010100000100000101000001000100010001000101000101000100010000010100010001010000010001000100000101

101010101010101110101011111010111011101011111011111010111110111110101111111110101111111110101011101111101011101110111110101111101110111010111010101010111111101111101110111111111011111010101010101110101

101010100010001000100010000010001010001000101010001010100000100010101000000000101000000010001000001010001000001000100010101000101000100010001010101010000000100000101000100000100000001000100010100010101

101010111111101011111111111011101010111110101010101110101111101010101111111110101011111011101111111010111111111011101010101010101010101111101011101011111110101110101010101110111111111011111110101011101

100010000010001000001000100010000010100010001000100000100000001010100010000000101000001000001000000000100000001010001010001010100010101000101000100010000010101010100010001000100010001000100010101000001

111110111110111011101010101110111111101001101111111111111111111010111010111111101111101111111011111111101111111010111011111010111110101110101110111110111010101010111111111011101010101110111010111011111

100010000000000010001010001010101000101000101000000000000000001010001000100000000000101000000010000000100000001010101000000010000000101000100000000010100010100010000010001010001000101000001010001010001

101011111011111110111011111010101010101110101011111111111110101011111111101111111010101010111110101110111111101010101111111111111111101011111111101110101110111110111010101011101111101111101011101110101

10101000100010000010100010000000101000101000100000001000001010100000100000100000001010001010000010001010000000100010000000000000100010100000000010100010000010001010001010100000100010000010*000100000101

101010101011101111101010001111111011111011111111111011111010111111101011111011111011111010111110111010101011111111101111111011101010101111101111101011111111101010101110111111111110111110111110111111101

101000101010001000100010101000001000000010000000100000001010000000100010100010000010000010000010001010001010001000001000001010001010001000001000101010000000101010101000000000100000000010001000000000101

101111101110111010101110111011101111111010111110111111101011111110111110101111111110111111011011101011111110101011111011101110111011111011111010101010111110101011101111111010101011101111101111111111101

101000101000101010100010000010001000001010001000000000100000000010000000100000000000000000001000101000000000100000001000101000100010001010000010101000100010001000101000000010101000101000100000000010001

101010101011101010111011111110111010111010101111111110101111111110111110111111111111111011111110111111111111111011111010101011101110101010111110101111111011111110101011111110111110101010111111111010101

10101000001000001000001000001000001000001010001000001010100000001010001010001000100000101000001000100000000000101000101010100010000*101000001000101000001000100*10101010000010000010101010001000000010101

101011111111111111111011101011111111111111101011101010101011111010101010111010101011101110111011101011111111101110101110101010111111101011111011101011101010101110101010111011111010111010111011111110111

101000100000000000001000001000001000000000101010001010101000100010101010001000101010100000100000100010001000101000100000101010000010101010000010001010000010101000101000001000101010000010001000001000001

101111101111111111101111111111101111111010111010111010101110101110101111101011101010111111101111111110111010101011111111101111101010101010111110111011111110101011101100111110101011111111101111101011101

100000001000000000100000000010100000000010001010001010101000101000100000101010001010000000100000000000001010001010001000000000001010101010001000100000100010101010000010100000101000000000000000101010001

101111111011111110111111111010101111111111101010101110111011101110101110101110101010111110111111111111101011111010101111111111111010101110101011111010101010101011101011101111101111111111111110101110101

101000000010001000000000101010001000100000100010100000100010100000101010100000101010100000100000000010100010001000100000100000000000100010101010001010001010101000101000100000100000000000001000101000101

101111101111101011111110101011111010101110111110111111101110111111101010101111111011101110111011111010111110101111101110101111111110111010101010101111111010101110111110111110101111111111101011101011111

101000100010001000001000001000100010001010000010001000001000100000100010101000000010001000000010001000100000100000100010101000100010100010100010100000000010100010000010000010100000000010001010001000001

101010111010111111101111101110101111111011111011101111101010101110111010101011111010111111111110101110101110111110111110101011101011101110111110111111111110101111111011111010111111101010111010111011101

100010001010100000001000100010100010000010001010000000001010101010000010001000000010000010000000100010101000100010000000100010001000001000000000100000000010100010001010000010000000101010001010001010001

111111101010101111101010111110111011101110101011111111111010101011111111111111111010111010111111101010101011101111111110111110111111111011111110111110111110111010101010111110111110101010111011101110111

100010001010101000001010100000101000100000101010001000000010000000001000000010000010100010000010001010101010000000000000100010101000000010000010100010000000001000101000101000100010101010100010100010001

101110111010101111111010101110101110111111101010101011111011111111101011101010111110101111111010101110101011101111101011101010101011111110111010101010111111101111101111101011101010111011101110111011101

100010001000100010001010101000100010000000001000101000001000001000001010001010100010101000001010101000101000101000101000001000101010001000101010101010100000100000001000000010001010001000001000101010001

111011101110111010101010101011101111111011111111101011111111101011111010111110101010101011101010001011101110111010111011111111101010111011101011101011101110101111111011111111101011101011111010101010111

100000101000001000101010001000100010000010001000001010000000101010000010001000101000100010101010101000100010000010001000100000101010001000001000001010001010101000000010000000001000101010000010001010001

101110101011111111101011111110111010111110101011111010111110101010111111101011111011111010101110101110111111111111101110101110101011101111101111111010111010111011111110011111101111101010111111101011101

100010101000100000001010000000000010100000100010000010100010100010001000100010001010001000101000100010000000000010000010101000101000000000100000100010000010001000000010001000001000101010001000101000101

101011101110101111111011111111111010101111111110111110111010101111101110111110101110101110101011111011111111111010111110101011101111111110111011101010111111101111111010101011111010101010101010111110101

101000101000101000000010*00000001010101000100010100010000010101000001000001000100010100010101010001000101000000010100010001010000010000010001010001010100010001000001010101010000010001010100010000010101

101110101111101011111010111111101110101010101010101111111010111011111011101011111010111010101011101110101011111110101011101010001011111011101010111110101010101110101011101110111111111011111111101110101

101010001000001000001010000000100000100010101010100000001010000010000010000010001010100010101000100000001010001000101000101010101000000010001010100010101000100000101010001000100000001010000000100010001

101001111011111111101111111110111111111110101010111111101011111110111011111110111010101111101010111111101010101110101110101010101111111110111010101010101011111111111010111011101111101010111110111011101

101000001000000000100000100010001010000010101010000010001000100000101000000010001000100000001010000010001000100010100010101010100000001000101010101010101010000000000010100010001000001000100010000000101

101011101111111011011011101011101010101110101111111010111110101111101111111010101111111111111111111011111111111010111010111010111111101011101010101010101010111111111110101110111011111111101010111111101

101010001000001000001000101000101010100010100000001000100010100000001000000010100000000000100000001010000000001010001010000010101000001000001010001010101010001000000000101010001000000000001000100000001

101010111011101111101110101011101010111010101011111011101010111110111011111111111011111110101111101010111110111010101011111110101011111011111011111010101111101010111111101011101111111111111111101111111

101010000010001000000010001010001000001010101000001010001000100000100010000000000010000010001000000010000010001000101010000000001000000010000010001000100010001010001000001000000000000010000000101000101

101011111110111011111011111010111110111010111011101010111111111111101110111110111110111011111011111111111011101111101011111111111011111110111110101110111010111011101011101111111111111010101111101010101

100010000000100000101000101010000010100010001000100010001000001000001000000010100000101000001000100000001010100000001010000010001010000010000010100000100010001000101000101000000000100000101000100010101

111110111111111110101110101011111011101011101111111111101011101011111011111011101111101111101111101111101010111111111010111010101110111011111010111110101011101111101110111011111110111111111010111110101

100000000000000000100000001000000000001000100000000000000010000010000000001000000000000000100000000000100000000000001000001000100000001000000000100000001000000000000010000000000010000000000010000000000

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

";

​

        // Разделяем строки и создаем двумерный массив символов для представления лабиринта

        string[] lines = input.Split('\n');

        char[,] maze = new char[lines.Length, lines[0].Length];

        for (int i = 0; i < lines.Length; i++)

        {

            for (int j = 0; j < lines[i].Length; j++)

            {

                maze[i, j] = lines[i][j];

            }

        }

​

        // Размеры лабиринта

        int rows = maze.GetLength(0);

        int cols = maze.GetLength(1);

​

        // Функция для проверки валидности ячейки

        bool IsValid(int x, int y)

        {

            return x >= 0 && x < rows && y >= 0 && y < cols && maze[x, y] != '1';

        }

​

        // Функция для получения следующего возможного шага

        List<Tuple<int, int>> GetNextSteps(int x, int y)

        {

            List<Tuple<int, int>> nextSteps = new List<Tuple<int, int>>();

            if (IsValid(x, y + 1))

            {

                nextSteps.Add(new Tuple<int, int>(x, y + 1));

            }

            if (IsValid(x + 1, y))

            {

                nextSteps.Add(new Tuple<int, int>(x + 1, y));

            }

            if (IsValid(x, y - 1))

            {

                nextSteps.Add(new Tuple<int, int>(x, y - 1));

            }

            if (IsValid(x - 1, y))

            {

                nextSteps.Add(new Tuple<int, int>(x - 1, y));

            }

            return nextSteps;

        }

​

        // Поиск пути к выходу

        Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();

        HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>();

        int maxItemsCollected = 0;

        List<Tuple<int, int>> maxItemsPath = new List<Tuple<int, int>>();

        stack.Push(new Tuple<int, int>(1, 0));

        while (stack.Count > 0)

        {

            Tuple<int, int> currentStep = stack.Peek();

            int x = currentStep.Item1;

            int y = currentStep.Item2;

            if (!visited.Contains(currentStep))

            {

                visited.Add(currentStep);

                if (maze[x, y] == '*')

                {

                    maxItemsCollected++;

                }

                if (x == rows - 2 && y == cols - 1)

                {

                    // Достигнут выход из лабиринта

                    if (maxItemsCollected > maxItemsPath.Count)

                    {

                        maxItemsPath = new List<Tuple<int, int>>(stack);

                    }

                }

                List<Tuple<int, int>> nextSteps = GetNextSteps(x, y);

                if (nextSteps.Count > 0)

                {

                    foreach (Tuple<int, int> nextStep in nextSteps)

                    {

                        stack.Push(nextStep);

                    }

                }

                else

                {

                    stack.Pop();

                }

            }

            else

            {

                stack.Pop();

            }

        }

​

        if (maxItemsCollected > 0)

        {

            Console.WriteLine("Маршрут к выходу с максимальным количеством собранных *:");

            foreach (Tuple<int, int> step in maxItemsPath)

            {

                Console.WriteLine($"({step.Item1},{step.Item2})");

                maze[step.Item1, step.Item2] = '*';

            }

            Console.WriteLine("Общее количество собранных *: " + maxItemsPath);

            for (int i = 0; i < rows; i++)

            {

                for (int j = 0; j < cols; j++)

                {

                    Console.Write(maze[i, j]);

                }

                Console.WriteLine();

            }

        } else

        {

Console.WriteLine("net vychoda");

        } }}