You are given a binary matrix n \times n consisting of zeroes and ones. Initially, you have an empty string . You start in the position (left-up corner) and move right or down. You append each element you have passed to the string in the respective order.
Tell whether it is possible to achieve being a palindrome. If yes, print the way it should pass to achieve that.
Note that each matrix is randomly generated.
The first line contains the only integer (1 \le n \le 5\,000) — the size of a matrix.
The following lines contain the characters a_{i,j} (0 \le a_{i,j} \le 1) — description of the matrix.
The input matrix for the problem is picked randomly across all possible valid matrices for the problem of size n \times n.
Print "NO" if there is no such palindrome.
Otherwise, in the first line, print "YES". In each of the following 2n-1 lines, print two integers x_i and y_i (0 \leq x_i, y_i < n) — the coordinates of the -th cell.
Example 1
Example 2
Example 3
( points) n \le 10;
( points) n \le 100;
( points) n \le 500;
( points) n \le 1\,500;
( points) no additional restrictions.