Treasure

Time limit2sMemory limit256 MB

Summary

Find all treasure cells on an N x N grid by asking rectangle count queries whose cost grows as the rectangle shrinks.

Level: Medium7 of 10
Topics: Divide and conquer, Binary search, Intervals, Greedy
Solved: No attempts yet

Problem

After a recent earthquake, a new island rose in the Adriatic Sea. Most of the island is barren, but archaeologists found a strange device that people now call the oracle. It came with no manual, yet a joint team of archaeologists and computer scientists figured out how it works.

The oracle reports where treasure is buried on the island. The island is an $N \times N$ grid. Rows and columns are numbered from 1 through $N$ . Some cells contain treasure. The oracle answers questions of the form: how many cells inside a given axis-aligned rectangle contain treasure?

If a rectangle covers $S$ cells, answering that question costs exactly $1 + N \times N - S$ energy. Smaller rectangles cost more.

Write a program that interacts with the oracle and finds every cell that contains treasure. Keep the total energy use low.

Interaction

Your program reads $N$ from standard input, then alternates queries and answers with the oracle.

Query: print one line with four integers $r_1\ c_1\ r_2\ c_2$ , the inclusive rectangle from row $r_1$ , column $c_1$ to row $r_2$ , column $c_2$ . ( $1 \le r_1 \le r_2 \le N$ , $1 \le c_1 \le c_2 \le N$ )

Answer: one line with the number of treasure cells inside that rectangle. A blank line follows each answer.

When every treasure cell is known, print END, then print the grid in $N$ lines. Each line is a length- $N$ string of 0 and 1. Use 1 for treasure and 0 for empty cells.

Constraints

$1 \le N \le 20$
The number of treasure cells is between 0 and $N \times N$ , inclusive.

Examples1

Example 1

Input

Expected output