Problem Description

Given an N x N chessboard, and several queens placed on it, determine if any pair of queens attack each other.

One queen is said to attack another if the attacked queen shares the same row, column or diagonal as the attacker, and there are no queens in between them.

Limits

Subtask 1 (15%): 1 ≤ N ≤ 50.

Subtask 2 (20%): 1 ≤ N ≤ 300.

Subtask 3 (30%): 1 ≤ N ≤ 2000, there are at most 2 queens on the board.

Subtask 4 (35%): 1 ≤ N ≤ 2000.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The next N lines of input will contain N characters each, with each character being either '.' (an empty square) or 'Q' (a queen), describing the grid.

Output

The output should contain either "Attack" or "No Attack", depending on whether there exists two queens attacking one another.

Sample Testcase 1

Input

4
Q...
..Q.
.Q..
...Q

Output

Attack

Sample Testcase 2

Input

8
...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q..

Output

No Attack