The capital of Berland has the only movie theater in the country. Besides, it consists of only one room. The room is divided into n rows, each row consists of m seats.

There are k people lined up to the box office, each person wants to buy exactly one ticket for his own entertainment. Before the box office started selling tickets, each person found the seat that seemed best for him and remembered it as a pair of coordinates (xi, yi), where xi is the row number, and yi is the seat number in this row.

It is possible that some people have chosen the same place, then when some people see their favorite seat taken in the plan of empty seats in the theater, they choose and buy a ticket to another place. Each of them has the following logic: let's assume that he originally wanted to buy a ticket to seat (x1, y1), then when he comes to the box office, he chooses such empty seat (x2, y2), which satisfies the following conditions: 

  * the value of |x1 - x2| + |y1 - y2| is minimum 
  * if the choice is not unique, then among the seats that satisfy the first condition, this person selects the one for which the value of x2 is minimum 
  * if the choice is still not unique, among the seats that satisfy the first and second conditions, this person selects the one for which the value of y2 is minimum 



Your task is to find the coordinates of a seat for each person.

Input

The first input line contains three integers n, m, k (1 ≤ n, m ≤ 2000, 1 ≤ k ≤ min(n·m, 105) — the number of rows in the room, the number of seats in each row and the number of people in the line, correspondingly. Each of the next k lines contains two integers xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) — the coordinates of the seat each person has chosen. Numbers on the same line are separated by a space. The pairs of coordinates are located in the order, in which people stand in the line, starting from the head (the first person in the line who stands in front of the box office) to the tail (the last person in the line).

Output

Print k lines, each containing a pair of integers. Print on the i-th line xi, yi — the coordinates of the seat, for which the person who stands i-th in the line will buy the ticket. 

Examples

Input

3 4 6
1 1
1 1
1 1
1 2
1 3
1 3


Output

1 1
1 2
2 1
1 3
1 4
2 3


Input

4 3 12
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2


Output

2 2
1 2
2 1
2 3
3 2
1 1
1 3
3 1
3 3
4 2
4 1
4 3
import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

import java.util.Arrays;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;

/**
 * Created by jizhe on 2015/12/21.
 */
public class Cinema {
    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

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

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

        public String nextString() {
            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 long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

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

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

    private static void run1()
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));

        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();

        //HashSet<Integer> seats = new HashSet<Integer>();
        boolean[][] seats = new boolean[2000][2000];
        for( int i = 0; i < 2000; i++ )
        {
            for( int j = 0; j < 2000; j++ )
            {
                seats[i][j] = false;
            }
        }
        int[] seatsRow = new int[100000];
        int[] seatsCol = new int[100000];

        for( int i = 0; i < K; i++ )
        {
            int row = in.nextInt();
            int col = in.nextInt();
            int number = 10000*row+col;
            //if( seats.contains(number) )
            if( seats[row-1][col-1] )
            {
                //System.out.printf("Seat has been sold: (%d, %d)\n", row, col);
                //get next seat
                int a = row-1;
                int b = N-row;
                int c = col-1;
                int d = M-col;
                int limit = Math.max(Math.max(Math.max(a+c, b+d), c+b), d+a);
                int dist;
                for( dist = 1; dist <= limit; dist++ )
                {
                    //System.out.printf("dist: %d\n", dist);
                    int dRow;
                    for( dRow = -dist; dRow <= dist; dRow++ )
                    {
                        //System.out.printf("dRow: %d\n", dRow);
                        int limit2 = dist-Math.abs(dRow);
                        int dCol;
                        if( limit2 == 0 ) {
                            dCol = 3 * limit2;
                            int nextRow = row + dRow;
                            int nextCol = col + 0;
                            if (nextRow >= 1 && nextRow <= N && nextCol >= 1 && nextCol <= M) {
                                //System.out.printf("Checking seat: (%d, %d)\n", nextRow, nextCol);
                                //int nextNumber = 10000 * nextRow + nextCol;
                                //if( !seats.contains(nextNumber) ) {
                                if (!seats[nextRow - 1][nextCol - 1]) {
                                    //System.out.printf("Sell seat: (%d, %d)\n", nextRow, nextCol);
                                    //seats.add(nextNumber);
                                    seats[nextRow - 1][nextCol - 1] = true;
                                    seatsRow[i] = nextRow;
                                    seatsCol[i] = nextCol;
                                    dCol = -1;
                                }
                            }
                        }
                        else {
                            for (dCol = -limit2; dCol <= limit2; dCol += 2 * limit2) {
                                int nextRow = row + dRow;
                                int nextCol = col + dCol;
                                if (nextRow >= 1 && nextRow <= N && nextCol >= 1 && nextCol <= M) {
                                    //System.out.printf("Checking seat: (%d, %d)\n", nextRow, nextCol);
                                    //int nextNumber = 10000 * nextRow + nextCol;
                                    //if (!seats.contains(nextNumber)) {
                                    if (!seats[nextRow-1][nextCol-1]) {
                                        //System.out.printf("Sell seat: (%d, %d)\n", nextRow, nextCol);
                                        //seats.add(nextNumber);
                                        seats[nextRow-1][nextCol-1] = true;
                                        seatsRow[i] = nextRow;
                                        seatsCol[i] = nextCol;
                                        break;
                                    }
                                }
                            }
                        }
                        if( dCol != 3*limit2 )
                        {
                            break;
                        }
                    }
                    if( dRow != dist+1 )
                    {
                        break;
                    }
                }
                //no chance to happen
                if( dist == limit+1 )
                {
                    System.out.printf("No seats to offer\n");
                }
            }
            else
            {
                //System.out.printf("Firstly encounter seat: (%d, %d)\n", row, col);
                //seats.add(number);
                seats[row-1][col-1] = true;
                seatsRow[i] = row;
                seatsCol[i] = col;
            }
        }

        for( int i = 0; i < K; i++ )
        {
            System.out.printf("%d %d\n", seatsRow[i], seatsCol[i]);
        }
    }

    //private static boolean[][] marked;

    private static boolean[][] marked = new boolean[2001][2001];
    private static int[][] nextSeatRow = new int[2001][2001];
    private static int[][] nextSeatCol = new int[2001][2001];

    //private static void getNextSeat(int rRow, int rCol, int cRow, int cCol, int N, int M, StringBuilder out)
    private static void getNextSeat(int rRow, int rCol, int cRow, int cCol, int N, int M, BufferedWriter out)
    {
        //System.out.printf("request seat: (%d, %d), current seat: (%d, %d)\n", rRow, rCol, cRow, cCol);

        int dRow = cRow - rRow;
        int dCol = cCol - rCol;
        int dist = Math.abs(dRow) + Math.abs(dCol);

        if( cRow == 0 )
        {
            dist = 0;
            dRow = 0;
            dCol = 0;
        }

        while( true )
        {
            int row = rRow+dRow;
            int col = rCol+dCol;

            //System.out.printf("Checking (%d, %d), diff: (%d, %d)\n", row, col, dRow, dCol);

            if( row >= 1 && row <= N && col >=1 && col <= M && !marked[row][col] ) {
                //System.out.printf("Sell seat: (%d, %d)\n", row, col);
                marked[row][col] = true;

                //out.append(row+" "+col+"\n");
                try {
                    out.write(row + " " + col + "\n");
                }catch (IOException e)
                {
                    e.printStackTrace();
                }

                nextSeatRow[rRow][rCol] = row;
                nextSeatCol[rRow][rCol] = col;
                return;
            }

            if( dRow == dist )
            {
                dist++;
                dRow = -dist;
                dCol = 0;
            }
            else if( dCol >= 0 )
            {
                dRow++;
                dCol = -dist+Math.abs(dRow);
            }
            else
            {
                dCol = -dCol;
            }
        }
    }

    private static void run2()
    {
        //Scanner in = new Scanner(new BufferedInputStream(System.in));
        FasterScanner in = new FasterScanner();

        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();

        /*int[][] nextSeatRow = new int[N][M];
        int[][] nextSeatCol = new int[N][M];
        marked = new boolean[N][M];*/

        //StringBuilder out = new StringBuilder();
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        for( int i = 0; i < K; i++ )
        {
            int rRow = in.nextInt();
            int rCol = in.nextInt();

            getNextSeat(rRow, rCol, nextSeatRow[rRow][rCol], nextSeatCol[rRow][rCol], N, M, out);
        }

        //System.out.print(out.toString());
        try {
            out.flush();
        }catch (IOException e)
        {
            e.printStackTrace();
        }

    }

    private static void run3()
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    public static void main(String[] args) {
        //run1();
        //run2();
        run3();
    }

    private static class TaskA {
        private static int n;
        private static int m;

        private static boolean[][] used;
        private static int[][] aNext;
        private static int[][] bNext;

        private static boolean swapped = false;

        public static void solve(int testNumber, InputReader jin, PrintWriter jout) {
            n = jin.int32();
            m = jin.int32();
            swapped = m < n;
            if(swapped) {
                n ^= m;
                m ^= n;
                n ^= m;
            }

            used = new boolean[n][m];

            aNext = new int[n][m]; ArrayUtils.init(aNext, -2);
            bNext = new int[n][m]; ArrayUtils.init(bNext, -2);

            for(int i = 0; i < n; i++) {
                aNext[i][m - 1] = -1;
                bNext[i][0] = -1;
            }

            int k = jin.int32();
            for(int i = 0; i < k; i++) {
                int x = jin.int32() - 1;
                int y = jin.int32() - 1;
                if(swapped && (x != y)) {
                    x ^= y; y ^= x; x ^= y;
                }
                int[] p = getNext(x, y);
                used[p[0]][p[1]] = true;
                if(swapped) {
                    jout.println((p[1] + 1) + " " + (p[0] + 1));
                } else {
                    jout.println((p[0] + 1) + " " + (p[1] + 1));
                }
            }

        }

        private static int[] getNext(int x, int y) {
            if(!used[x][y]) return new int[]{x, y};

            int gx = -1;
            int gy = -1;
            int diff = Integer.MAX_VALUE;
            for(int i = 0; i < n; i++) {
                if(i > diff) break;
                for(int j = -1; j <= 1; j++) {
                    if(j == 0) continue;
                    int nx = x + (j * i);
                    if(nx < 0 || nx >= n) continue;
                    int ny = after(nx, y);
                    if(ny != -1) {
                        if (isBetter(nx, ny, gx, gy, x, y)) {
                            gx = nx;
                            gy = ny;
                            diff = dist(gx, gy, x, y);
                        }
                    }
                    ny = before(nx, y);
                    if(ny != -1) {
                        if (isBetter(nx, ny, gx, gy, x, y)) {
                            gx = nx;
                            gy = ny;
                            diff = dist(gx, gy, x, y);
                        }
                    }
                }
            }

            return new int[]{gx, gy};
        }

        private static boolean isBetter(int nx, int ny, int gx, int gy, int x, int y) {
            if(nx == -1 || ny == -1) return false;
            if(gx == -1 || gy == -1) return true;
            int d1 = dist(nx, ny, x, y);
            int d2 = dist(gx, gy, x, y);
            if(d1 == d2) {
                if(!swapped) {
                    if (nx == gx) {
                        return ny < gy;
                    }
                    return nx < gx;
                } else {
                    if (ny == gy) {
                        return nx < gx;
                    }
                    return ny < gy;
                }

            }
            return d1 < d2;
        }

        private static int dist(int nx, int ny, int x, int y) {
            return Math.abs(nx - x) + Math.abs(ny - y);
        }

        private static int before(int x, int y) {
            if(!used[x][y]) return y;
            if(bNext[x][y] == -1) return -1;
            if(bNext[x][y] == -2) bNext[x][y] = y - 1;
            if(used[x][bNext[x][y]])
                return bNext[x][y] = before(x, bNext[x][y]);
            return bNext[x][y];
        }

        private static int after(int x, int y) {
            if(!used[x][y]) return y;
            if(aNext[x][y] == -1) return -1;
            if(aNext[x][y] == -2) aNext[x][y] = y + 1;
            if(used[x][aNext[x][y]])
                return aNext[x][y] = after(x, aNext[x][y]);
            return aNext[x][y];
        }

    }

    private static class InputReader {
        private static final int bufferMaxLength = 1024;
        private InputStream in;
        private byte[] buffer;
        private int currentBufferSize;
        private int currentBufferTop;
        private static final String tokenizers = " \t\r\f\n";

        public InputReader(InputStream stream) {
            this.in = stream;
            buffer = new byte[bufferMaxLength];
            currentBufferSize = 0;
            currentBufferTop = 0;
        }

        private boolean refill() {
            try {
                this.currentBufferSize = this.in.read(this.buffer);
                this.currentBufferTop = 0;
            } catch(Exception e) {}
            return this.currentBufferSize > 0;
        }


        public Byte readChar() {
            if(currentBufferTop < currentBufferSize) {
                return this.buffer[this.currentBufferTop++];
            } else {
                if(!this.refill()) {
                    return null;
                } else {
                    return readChar();
                }
            }
        }

        public String token()  {
            StringBuffer tok = new StringBuffer();
            Byte first;
            while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) != -1));
            if(first == null) return null;
            tok.append((char)first.byteValue());
            while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) == -1)) {
                tok.append((char)first.byteValue());
            }
            return tok.toString();
        }


        public String next() {
            return token();
        }

        public Integer int32() throws NumberFormatException {
            String tok = token();
            return tok == null? null : Integer.parseInt(tok);
        }

        public Long int64() throws NumberFormatException {
            String tok = token();
            return tok == null? null : Long.parseLong(tok);
        }
    }

    private static class  ArrayUtils {

        public static void init(int[][][] arr, int val) {
            for(int[][] subarr: arr)
                ArrayUtils.init(subarr, val);
        }

        public static void init(int[][] arr, int val) {
            for(int[] subarr: arr)
                ArrayUtils.init(subarr, val);
        }

        public static void init(int[] arr, int val) {
            Arrays.fill(arr, val);
        }

        public static int accumulate(int[] arr) {
            int res = 0;
            for(int xx: arr)
                res += xx;
            return res;
        }

        public static void init(double[][] arr, double val) {
            for(double[] subarr: arr)
                ArrayUtils.init(subarr, val);
        }

        private static void init(double[] arr, double val) {
            Arrays.fill(arr, val);
        }

        public static void init(long[][] arr, long val) {
            for(long[] subarr: arr)
                ArrayUtils.init(subarr, val);
        }

        private static void init(long[] subarr, long val) {
            Arrays.fill(subarr, val);
        }
    }

}
