В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.
Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.
Примечание:
1 команда (повернуть на 90 градусов по часовой стрелке)
2 команда (повернуть на 45 градусов по часовой стрелке)
| 0 |
0 |
7 |
0 |
0 |
| 0 |
8 |
0 |
4 |
0 |
| 9 |
0 |
5 |
0 |
1 |
| 0 |
6 |
0 |
2 |
0 |
| 0 |
0 |
3 |
0 |
0 |
3 команда (повернуть на 90 градусов по часовой стрелке)
| 0 |
0 |
9 |
0 |
0 |
| 0 |
6 |
0 |
8 |
0 |
| 3 |
0 |
5 |
0 |
7 |
| 0 |
2 |
0 |
4 |
0 |
| 0 |
0 |
1 |
0 |
0 |
4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))
Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
4 5 6
7 8 9
4
1
3
1
4
|
18 12
|