Иннокентий решил поиграть в следующую забавную игру: Дано поле N x M клеток (высота - N клеток, ширина - M клеток). Пусть клетка (x, y) - это клетка в x-м ряду и y-м столбце (ряды нумеруются сверху-вниз, а столбцы слева-направо). Изначально в клетке (1, 1) лежит S камней (S >= 4), нужно эти камни переместить в клетку (N, M). Игра поделена на ходы, каждый ход Иннокентий должен из каждой клетки поля какую-то часть камней переместить на 1 клетку вверх/вправо/вниз/влево, а какую-то часть оставить в данной клетке, части могут быть нулевыми (не содержать ни одного камня), также сумма по количеству камней в частях должна равняться изначальному количеству камней в клетке, а также камни не могут выходить за границы поля. Стоит заметить, что Иннокентий применяет передвижения для всех клеток одновременно.

Формальные правила: Пусть до совершения хода в i-й строке, j-м столбце будет a[i][j] камней, и пусть правило перемещения камней для этой клетки задается 4-мя числами: b[i][j][0], b[i][j][1], b[i][j][2], b[i][j][3] - количество камней которое переместиться из клетки (i, j) в клетку (i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1) соответственно (b[i][j][0] + b[i][j][1] + b[i][j][2] + b[i][j][3] <= a[i][j]). Пусть после совершения хода в i-й строке, j-м столбце будет с[i][j] камней тогда

с[i][j] = a[i][j] - (b[i][j][0] + b[i][j][1] + b[i][j][2] + b[i][j][3]) + b[i + 1][j][0] + b[i][j - 1][1] + b[i + 1][j][2] + b[i][j + 1][3]. Считаем, что b[i][j][k] = 0, для i, j выходящих за пределы (1..N) и (1..M) соответственно. Игра считается выигранной, если существует ход с номером меньшим либо равным H, такой что, на этом ходу b[N][M] станет равным S, и после этого хода не будет совершаться никаких перемещений. *Ходы пронумерованы от 1-го до H-го.

Однако Иннокентий быстро понял, что данная игра является слишком простой для него. И он придумал себе некоторые ограничения, для усложнения игры. Во первых, теперь вместо того, что-бы задавать правило для каждой отдельной клетки, он теперь задает правило для каждого возможного количества камней в клетках, то-есть для каждого z (количество камней в клетке), придумывает правило, состоящие из 4-х чисел: d[z][0], d[z][1], d[z][2], d[z][3]. И тогда на каждом ходу происходит перемещения камней по "формальным правилам", но b[i][j][k] = d[a[i][j]][k] для всех i, j, k. Также b[i][j][k] = 0, вне зависимости от d[a[i][j]][k], если для данных i, j, k клетка куда должны переходить b[i][j][k] камней выходит за границы поля.

Вскоре Иннокентию наскучила игра и с такими ограничениями, и поэтому он захотел разобраться с данной игрой раз и навсегда придумав такую стратегию (то-есть такие d[z][0], d[z][1], d[z][2], d[z][3] для каждого z), которая будет выигрывать игру при всех возможных полях (то-есть для всех N, M: 1 <= N <= MAXN, 1 <= M <= MAXM), и при всех возможных начальных количествах камней (то-есть для всех S: 4 <= S <= MAXS).