Максим Витальевич очень любит играть в игры, точнее, в одну конкретную игру. Максим Витальевич проводил так много времени в этой игре, что в последнее время она ему надоела, и он решил сделать перерыв. Если точнее, то Максим Витальевич решил найти другую интересную игру.

После усердного поиска в интернете Максим Витальевич наткнулся на увлекательную игру-головоломку. В данной игре есть несколько уровней. На картинке ниже изображен пример уровня.

Каждый уровень представлен клетчатым полем размера $$$n \times m$$$, где $$$n$$$ – количество строк, а $$$m$$$ – количество столбцов. Каждая клетка этого поля либо свободна, либо занята препятствием, котом, котенком или собакой. На поле всегда находятся ровно один кот и один котенок, а также не более одной собаки. Игрок управляет передвижениями кота. Чтобы пройти уровень, игроку необходимо спасти котенка: за некоторое количество ходов переместить кота в клетку с котенком. За один ход игрок может переместить кота на соседнюю по горизонтали либо вертикали клетку, при этом он не может перемещать кота в клетку с препятствием. Если после хода кот оказался в клетке с котенком, то уровень считается пройденным. Если после хода кот оказался в клетке с собакой, то уровень считается непройденным (и его придется проходить заново).

После каждого хода игрока, при наличии собаки на поле, она осуществляет два хода. За один ход собака сближается с котом на одну клетку либо по вертикали, либо по горизонтали, при этом она не может перемещаться в клетку с препятствием. В качестве расстояния используется Манхэттенское расстояние между котом и собакой. Если собака может сблизиться и по горизонтали, и по вертикали, то она всегда сблизится по горизонтали (переместится либо влево, либо вправо). Если собака не может сблизиться, то она пропускает ход. Обратите внимание, что собака не может отдаляться от кота. Если собака после хода оказалась в клетке с котом, то уровень считается непройденным. Собака может перемещаться в клетку с котенком, при этом, если игрок переместится в клетку с котенком и собакой, то уровень также считается непройденным.

Максим Витальевич застрял на одном из уровней. Помогите Максиму Витальевичу пройти уровень, либо скажите, что данный уровень пройти нельзя.