Table Game

Time limit1sMemory limit256 MB

Summary

Two players alternately lower numbers in one row, and the player with no legal move loses, so determine the winner under optimal play.

Level: Medium7 of 10
Topics: Game theory, Bit manipulation, Math
Solved: No attempts yet

Problem

august14 and ainta play a table game. The game starts from a table of size $N \times M$ filled with numbers. The two players take turns.

On your turn you pick one row of the table. You then decrease the numbers in the columns of that row. The amount you subtract may differ from column to column, and you may leave some columns unchanged, but you must decrease at least one column. You may not make any number smaller than 0.

For example, suppose the table is this.

2 3 8
5 2 7

august14 can pick row 2 and subtract 2 at (2, 1), 0 at (2, 2), and 7 at (2, 3). The table then becomes this.

2 3 8
3 2 0

A player who has no row left to decrease on their turn loses the game.

Given the numbers filled into the table, write a program that finds the winner when august14 and ainta both play optimally. august14 moves first.

Input

The first line contains the number of rows $N$ and the number of columns $M$ . ( $1 \le N, M \le 50$ )

Each of the next $N$ lines contains one row of the table, in order from row 1. Every number in the table is an integer between 0 and $10^9$ , inclusive.

Output

Print "august14" if august14 wins, or "ainta" if ainta wins.

Examples2

Example 1
Input
```
2 3
2 3 8
5 2 7
```
Expected output
```
august14
```
Example 2
Input
```
2 3
1 2 3
3 2 1
```
Expected output
```
ainta
```