Randomized Palindromes#399

Randomized Palindromes

1 seconde
256 mégaoctets
Very hard

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.

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Scoring

  1. ( points) n \le 10;

  2. ( points) n \le 100;

  3. ( points) n \le 500;

  4. ( points) n \le 1\,500;

  5. ( points) no additional restrictions.