시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 34 20 19 59.375%

문제

august14와 ainta가 표 게임을 하고 있다. 표 게임은 n×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 ≤ N, M ≤ 50), 둘째 줄부터 N개의 줄에는 표의 내용이 1행부터 순서대로 주어진다. 표에 채워져 있는 수는 0보다 크거나 같고, 109보다 작거나 같은 정수이다.

출력

august14가 이기는 경우에는 "august14"를, ainta가 이기는 경우에는 "ainta"를 출력한다.

예제 입력

2 3
2 3 8
5 2 7

예제 출력

august14

예제 입력 2

2 3
1 2 3
3 2 1

예제 출력 2

ainta

힌트

출처