Background

The interactive library is extremely smart.

Problem Description

Rules of Pig Chess:

On a $1000\times 1000$ board, two players take turns playing Black and White. In each turn, the current player may place two pieces on two different empty positions on the board (ordered). If, when a piece is placed, the four positions $(x,y),(x+1,y),(x,y+1),(x+1,y+1)$ all contain pieces of the same color, then the player of that color wins.

You will play as the first player, and you need to defeat the interactive library (playing as the second player) within $100$ moves. A solution is guaranteed to exist.

In each round, you may choose two coordinates $(x_1,y_1)$ and $(x_2,y_2)$ to place your pieces. First, you must ensure $1\leq x_1,y_1,x_2,y_2\leq 1000$. Next, you must ensure that no one has ever placed a piece at $(x_1,y_1)$. If you win at this point, the judging ends and you win. Otherwise, you must also ensure that no one has ever placed a piece at $(x_2,y_2)$. If you win at this point, the judging ends and you win. Otherwise, the interactive library will return a set of $x_1,y_1,x_2,y_2$, meaning it places pieces at $(x_1,y_1)$ and $(x_2,y_2)$. It is guaranteed that $(x_1,y_1)\neq (x_2,y_2)$ and $1\leq x_1,y_1,x_2,y_2\leq 1000$. If the interactive library wins at this point, the judging ends and you lose. Otherwise, it will check whether there are already $400$ pieces on the board. If yes, you get a draw; otherwise, it enters your next round.

Input Format

After each round ends, read four integers from standard input, representing the result returned by the judge.

Output Format

At the beginning of each round, output four integers in $[1,1000]$ to standard output, and then flush the buffer.

You may use the following statements to flush the buffer:

• For C/C++: fflush(stdout)；
• For C++: std::cout << std::flush；
• For Java: System.out.flush()；
• For Python: stdout.flush()；
• For Pascal: flush(output)；
• For other languages, please check the documentation of the corresponding language.

In particular, for C++, when outputting a newline, if you use std::endl instead of '\n', it can also flush the buffer automatically.

Hint

There are $5$ test points. In a test point, if you win and in every step you satisfy $6\leq x,y\leq 994$, you will get $100$ points; otherwise, if you win you will get $50$ points; if you lose you will get $0$ points; if you draw you will get $30$ points. The final score is the minimum over all test points.

Reference I/O $0$-point program for this problem:

#include <bits/stdc++.h>

using namespace std;

int n;
int x,y,xx,yy;


signed main()
{
    int i,j,k;
    n=100;
    while(n--)
    {
        cout<<rand()%1000+1<<' '<<rand()%1000+1<<endl;
        cout<<rand()%1000+1<<' '<<rand()%1000+1<<endl;
        cin>>x>>y>>xx>>yy;
    }
    return 0;
}

Translated by ChatGPT 5