All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
As a cryptologist, after working on numerous cryptographic protocols, Alice is now retired and living happily in Wonderland. However Alice is still obsessed with security, she even invented a new way to set passwords. Given a board of n rows and n columns with unitary size cells, Alice creates a password by drawing exactly n+1 lines with vertices of the integer points on the perimeter of the board.
One day Alice forgot her CodeChef password! She knew that she had set her password in the secure way. She remembers that no two lines were parallel, and that every cell of the board was cut by at least one of the lines. A cell is cut by a line when there exists a point strictly inside of the cell that belongs to the line.
Please help Alice finding one password satisfying the information that she remembered.
The first line of the input contains one integer T the number of test cases.
Each test case is described by a line containing an integer n representing the size of the board.
For each test case print n + 1 lines each of them containing four integers x1 y1 x2 y2 with x1 ≠ x2 and y1 ≠ y2, representing a line that goes from (x1,y1) to (x2,y2).
If there are multiple passwords that satisfies the information, print any of them.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 103
Input: 1 3 Output: 0 0 3 2 3 0 0 2 0 1 2 3 0 3 3 2
One of the possible passwords is depicted in the above figure.
Every cell is cut by at least one line, for example the green cell is cut by the blue and purple lines, but not by the yellow one. The integer points on the perimeter of the board are drawn as small black circles.
|Tags||alei, constructive, cook73, easy-medium, gcd|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.