Ashish и Vivek играют в игру на таблице с \(n\) строками и \(m\) столбцами, захватывая клетки. Незахваченные клетки обозначены \(0\), а захваченные клетки обозначены \(1\). Вам дано исходное состояние таблицы.
На каждом ходу, игрок должен захватить одну клетку. Клетку можно захватить, если она еще не захвачена, и она не находится в одной строке или столбце с другой захваченной клеткой. Игра кончается, когда игрок не может сделать ход, в таком случае, он проигрывает.
Если Ashish и Vivek ходят по очереди и Ashish ходит первым, найдите победителя игры если они оба играют оптимально.
Оптимальная игра между двумя игроками означает, что оба игрока выбирают лучшую возможную стратегию, чтобы получить наиболее благоприятный для себя результат игры.
Выходные данные
Для каждого набора входных данных, если Ashish выиграет при правильной игре, выведите «Ashish», иначе выведите «Vivek» (без кавычек).
Примечание
В первом наборе входных данных: Один из возможных исходов игры следующий: Ashish захватывает клетку \((1, 1)\), затем Vivek захватывает клетку \((2, 2)\). Ashish не может захватить ни клетку \((1, 2)\), ни клетку \((2, 1)\), так как клетки \((1, 1)\) и \((2, 2)\) уже захвачены. Таким образом, Ashish проигрывает. Можно показать, что вне зависимости от ходов Ashish, Vivek выиграет. Во втором наборе входных данных: Ashish захватывает клетку \((1, 1)\), единственная клетка, которую можно захватить. После этого у Vivek не будет возможных ходов.
В третьем наборе входных данных: Ashish не может сделать ход, поэтому Vivek выиграет.
В четвертом наборе входных данных: Ashish захватывает клетку \((2, 3)\), у Vivek не останется возможных ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0
|
Vivek
Ashish
Vivek
Ashish
|