Problem: This is an interactive task.

Dasha and NN like playing chess. While playing a match they decided that normal chess isn't interesting enough for them, so they invented a game described below.

There are 666 black rooks and 1 white king on the chess board of size 999 × 999. The white king wins if he gets checked by rook, or, in other words, if he moves onto the square which shares either a row or column with a black rook.

The sides take turns, starting with white. NN plays as a white king and on each of his turns he moves a king to one of the squares that are adjacent to his current position either by side or diagonally, or, formally, if the king was on the square (x, y), it can move to the square (nx, ny) if and only max (|nx - x|, |ny - y|) = 1 , 1 ≤ nx, ny ≤ 999. NN is also forbidden from moving onto the squares occupied with black rooks, however, he can move onto the same row or column as a black rook.

Dasha, however, neglects playing by the chess rules, and instead of moving rooks normally she moves one of her rooks on any space devoid of other chess pieces. It is also possible that the rook would move onto the same square it was before and the position wouldn't change. However, she can't move the rook on the same row or column with the king.

Each player makes 2000 turns, if the white king wasn't checked by a black rook during those turns, black wins. 

NN doesn't like losing, but thinks the task is too difficult for him, so he asks you to write a program that will always win playing for the white king. Note that Dasha can see your king and play depending on its position.

Input

In the beginning your program will receive 667 lines from input. Each line contains two integers x and y (1 ≤ x, y ≤ 999) — the piece's coordinates. The first line contains the coordinates of the king and the next 666 contain the coordinates of the rooks. The first coordinate denotes the number of the row where the piece is located, the second denotes the column. It is guaranteed that initially the king isn't in check and that all pieces occupy different squares.

Output

After getting king checked, you program should terminate immediately without printing anything extra.

Interaction

To make a move with the king, output two integers x and y (1 ≤ x, y ≤ 999) — the square to which the king would be moved. The king cannot move onto the square already occupied by a rook. It is guaranteed that the king would always have a valid move.

After each of your turns read the rook's turn in the following format: a single line containing three integers k, x and y (1 ≤ k ≤ 666, 1 ≤ x_i, y_i ≤ 999) — the number of the rook that would move and the square it would move to. It is guaranteed that the rook wouldn't move to a square already occupied by another chess piece, but it can move onto the square where it was before the turn so that its position wouldn't change. It is guaranteed that the move does not put your king into a check. If your king got in check, all three integers would be equal to -1 and in that case your program should terminate immediately.

After printing your turn do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Answer "0 0 0" instead of a correct answer means that you made an invalid query. Exit immediately after receiving "0 0 0" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks are not allowed for this problem.

Example

Input

999 999
1 1
1 2
2 1
2 2
1 3
2 3
&lt;...&gt;
26 13
26 14
26 15
26 16

1 700 800

2 1 2

&lt;...&gt;

-1 -1 -1


Output












999 998

999 997

&lt;...&gt;

999 26

Note

The example is trimmed. The full initial positions of the rooks in the first test are available at <https://pastebin.com/qQCTXgKP>. It is not guaranteed that they will behave as in the example.

Solution (in JAVA):

Solution:
// package cf1100;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.InputMismatchException;

public class CFD {
    private static final String INPUT = "5 5\n" +
            "1 1\n" +
            "1 9\n" +
            "9 1\n" +
            "9 9\n" +
            "1 2\n" +
            "9 8\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n" +
            "1 1 1\n";
    public static final int SIZE = 999;
    public static final int LADSIZE = 666;

    private PrintWriter out;
    private FastScanner sc;

    public static void main(String[] args) {
        new CFD().run();
    }

    public void run() {
        sc = new FastScanner(oj ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }

    public void solve() {
        int kx = sc.nextInt();
        int ky = sc.nextInt();

        int topleft = 0;
        int botleft = 0;
        int toprigh = 0;
        int botrigh = 0;
        int[] hor = new int[SIZE+1];
        int[] ver = new int[SIZE+1];
        int[] ladx = new int[LADSIZE+1];
        int[] lady = new int[LADSIZE+1];
        for (int i = 1; i <= LADSIZE; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            ladx[i] = x;
            lady[i] = y;
            hor[y]++;
            ver[x]++;

            if (x <= (SIZE+1)/2) {
                if (y <= (SIZE+1)/2) {
                    topleft++;
                } else {
                    botleft++;
                }
            } else {
                if (y <= (SIZE+1)/2) {
                    toprigh++;
                } else {
                    botrigh++;
                }
            }
        }

        int cmd = 0; //goto center (500,500)
        while(true) {
            if (ky < SIZE && hor[ky + 1] > 0) {
                System.out.println(kx + " " + ++ky);
                System.out.flush();
                return;
            } else if(ky > 1 && hor[ky - 1] > 0) {
                System.out.println(kx + " " + --ky);
                System.out.flush();
                return;
            } else if (kx < SIZE && ver[kx + 1] > 0) {
                System.out.println(++kx + " " + ky);
                System.out.flush();
                return;
            } else if (kx > 1 && ver[kx - 1] > 0) {
                System.out.println(--kx + " " + ky);
                System.out.flush();
                return;
            }

            if (cmd == 0) { //got center
                if (kx < (SIZE+1)/2) {
                    System.out.println(++kx + " " + ky);
                    System.out.flush();
                } else if (kx > (SIZE+1)/2) {
                    System.out.println(--kx + " " + ky);
                    System.out.flush();
                } else if (ky < (SIZE+1)/2) {
                    System.out.println(kx + " " + ++ky);
                    System.out.flush();
                } else if (ky > (SIZE+1)/2) {
                    System.out.println(kx + " " + --ky);
                    System.out.flush();
                } else { //center
                    if (topleft + botleft + toprigh >= (SIZE)/2) {
                        cmd = 1; //topleft
                    } else if (topleft + botleft + botrigh >= (SIZE)/2) {
                        cmd = 2; //botleft
                    } else if (toprigh + botrigh + topleft >= (SIZE)/2) {
                        cmd = 3; //toprigh
                    } else if (toprigh + botrigh + botleft >= (SIZE+1)/2) {
                        cmd = 4; //botleft
                    }
                }
            }
            if (cmd == 1) { //topleft
                System.out.println(--kx + " " + --ky);
                System.out.flush();
            } else if (cmd == 2) { //botleft
                System.out.println(--kx + " " + ++ky);
                System.out.flush();
            } else if (cmd == 3) { //toprigh
                System.out.println(++kx + " " + --ky);
                System.out.flush();
            } else if (cmd == 4) { //botrigh
                System.out.println(++kx + " " + ++ky);
                System.out.flush();
            }
            if (ver[kx] > 0 || hor[ky] > 0) return;

            int nr = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            if (nr == 0 && x == 0 && y == 0) {
                return;
            }

            ver[ladx[nr]]--;
            hor[lady[nr]]--;
            if (ladx[nr] <= (SIZE+1)/2) {
                if (lady[nr] <= (SIZE+1)/2) {
                    topleft--;
                } else {
                    botleft--;
                }
            } else {
                if (lady[nr] <= (SIZE+1)/2) {
                    toprigh--;
                } else {
                    botrigh--;
                }
            }
            ver[x]++;
            hor[y]++;
            ladx[nr] = x;
            lady[nr] = y;
            if (ladx[nr] <= (SIZE+1)/2) {
                if (lady[nr] <= (SIZE+1)/2) {
                    topleft++;
                } else {
                    botleft++;
                }
            } else {
                if (lady[nr] <= (SIZE+1)/2) {
                    toprigh++;
                } else {
                    botrigh++;
                }
            }
        }
    }

    //********************************************************************************************
    //********************************************************************************************
    //********************************************************************************************

    /**
     * If searched element doesn't exist, returns index of first element which is bigger than searched value.<br>
     * If searched element is bigger than any array element function returns first index after last element.<br>
     * If searched element is lower than any array element function returns index of first element.<br>
     * If there are many values equals searched value function returns first occurrence.<br>
     */
    private static int lowerBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key <= arr[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return arr[lo] < key ? lo + 1 : lo;
    }

    /**
     * Returns index of first element which is grater than searched value.
     * If searched element is bigger than any array element, returns first index after last element.
     */
    private static int upperBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key >= arr[mid]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return arr[lo] <= key ? lo + 1 : lo;
    }

    private static int ceil(double d) {
        int ret = (int) d;
        return ret == d ? ret : ret + 1;
    }

    private static int round(double d) {
        return (int) (d + 0.5);
    }

    private static int gcd(int a, int b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }

    private static long gcd(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }

    private int[] readIntArray(int n) {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextInt();
        }
        return res;
    }

    private long[] readLongArray(int n) {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextLong();
        }
        return res;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        boolean isEndline(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }

    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }
}