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