Глеб очень любит компьютерные игры, потому решил впервые разработать свою игру. Он начал с чего-то максимально простого – матричного пинг-понга. Первым этапом Глеб решил сделать алгоритм, который будет считать количество набранных очков мячиком, который будет запускаться в матрице, состоящей из целых чисел.
Для того, чтобы протестировать алгоритм, Глеб указывает стартовую позицию мячика и его стартовое направление (число от 1 до 8). Мячик после прохождения через ячейку матрицы оставляет на её месте дыру, при попадании в будущем в которую игра заканчивается.
Стоит также учесть, что так как это пинг-понг, то мячик отталкивается от стенок, но в данной игре отражение действует по принципу угол отражения равен углу преломления + 45 градусов по часовой стрелке (при попадании в угол мячик отталкивается в обратном направлении + 45 градусов). Если мячик попадает в угол под углом 45 градусов, то он отражается обратно вектору попадания.
Стартовое направление мячика задаётся числом от 1 до 8. Направления представлены в виде матрицы ниже, где x – это текущая позиция мячика.
Входные данные
В первой строке подаются два числа N, M (1 <= N, M <= 100) – размер матрицы, далее на N строках по M целых чисел (от -10000 до 10000) вводится сама матрица. После вводится на одной строке стартовая позиция мячика (нумерация в матрице с 1), а на последней строке вводится стартовое направление мячика (число от 1 до 8).
Выходные данные
Вывести в ответе единственное число – количество набранных очков мячиком после старта.
Примечание
Пример №2: При старте из ячейки -5 по направлению 8 (в правый нижний угол), мячик ударится в угол, значит он должен отразиться в обратном направлении, но так как к углу отражения по правилам игры прибавляется 45 градусов по часовой стрелке, то мячик полетит по направлению не 1 (в левый верхний угол), а по направлению 2 (вверх). Далее отразится в обратном направлении от верхней стенки и попадёт в ячейку -5, на месте которой уже осталась дыра, потому игра окончится.