Piet — один из самых известных визуальных эзотерических языков программирования. Программы на нем составляются из разноцветных блоков пикселей и интерпретируются по довольно сложным правилам. В этой задаче мы рассмотрим подмножество языка Piet с упрощенными правилами.

Программа будет прямоугольным изображением, состоящим из цветных и черных пикселей. Цвет каждого пикселя будет задаваться целым числом от 0 до 9. Цвет 0 соответствует черному цвету. Блок пикселей определяется как прямоугольник, состоящий из пикселей одного цвета (не черного). Гарантируется, что все связные множества цветных пикселей будут образовывать прямоугольные блоки. Группы черных пикселей могут иметь произвольную форму.

В процессе интерпретации программы по ней двигается счетчик инструкций, состоящий из трех частей:

• указателя на текущий блок (англ. block pointer, далее BP); текущий пиксель в блоке не выделяется;
• указателя направления (англ. direction pointer, далее DP), который может указывать вверх, вниз, влево и вправо;
• указателя выбора блоков (англ. block chooser, далее CP), который может указывать влево или вправо относительно DP (в абсолютных направлениях — отличаться от DP на 90 градусов против или по часовой стрелке, соответственно).

Изначально BP указывает на блок, которому принадлежит верхний левый пиксель программы, DP указывает вправо, а CP — влево относительно DP (см. оранжевый квадрат на рисунке ниже).

Один шаг изменения состояния счетчика происходит следующим образом. Для текущего блока находится его край в направлении DP. Из всех пикселей края выбирается крайний в направлении CP. Затем BP пытается переместиться из этого пикселя в соседний в направлении DP. Если соседний пиксель принадлежит цветному блоку (цвета, отличного от 0), этот блок становится текущим, а два других указателя сохраняют свои значения. Если же соседний пиксель имеет черный цвет (0) или находится за пределами программы, текущий блок остается прежним, а меняются направления двух других указателей следующим образом. Если CP указывал влево, теперь он указывает вправо, а DP не меняется. Если CP указывал вправо, то теперь он указывает влево, а DP поворачивается на 90 градусов по часовой стрелке.

Таким образом, текущий блок никогда не будет черного цвета. Гарантируется, что верхний левый блок программы не будет черным.

Вам дана программа на Piet. Определите, какой блок программы будет текущим через n шагов.