표 게임

시간 제한1초메모리 제한256 MB

요약

두 명이 번갈아 한 행의 수를 줄이며 더 이상 줄일 수 없는 사람이 지는 게임의 승자를 구합니다.

문제

august14와 ainta가 표 게임을 한다. 표 게임은 $N \times M$ 크기의 표에 수를 채워 놓고 시작한다. 두 사람은 턴을 번갈아 가며 진행한다.

자기 턴이 되면 표에서 행을 하나 고른다. 그 다음 고른 행의 각 열에 있는 수를 감소시킨다. 감소시키는 값은 열마다 달라도 되고 어떤 열은 그대로 두어도 되지만, 적어도 한 열은 반드시 감소시켜야 한다. 또 수를 0보다 작게 만들 수는 없다.

예를 들어 표가 다음과 같다고 하자.

2 3 8
5 2 7

august14는 2행을 고른 뒤 (2, 1)에서 2를, (2, 2)에서 0을, (2, 3)에서 7을 감소시킬 수 있다. 그러면 표는 다음과 같이 바뀐다.

2 3 8
3 2 0

자기 턴에 감소시킬 수 있는 행이 하나도 없으면 그 사람이 게임에서 진다.

표에 채워진 수가 주어졌을 때, august14와 ainta가 최적으로 게임을 진행하면 누가 이기는지 구하는 프로그램을 작성하시오. 게임은 august14가 먼저 시작한다.

첫째 줄에 행의 개수 $N$ 과 열의 개수 $M$ 이 주어진다. ( $1 \le N, M \le 50$ )

둘째 줄부터 $N$ 개 줄에 걸쳐 표의 내용이 1행부터 순서대로 주어진다. 표에 채워진 수는 0보다 크거나 같고 $10^9$ 보다 작거나 같은 정수이다.

august14가 이기면 "august14"를, ainta가 이기면 "ainta"를 출력한다.