This morning Tolik has understood that while he was sleeping he had invented an incredible problem which will be a perfect fit for Codeforces! But, as a "Discuss tasks" project hasn't been born yet (in English, well), he decides to test a problem and asks his uncle.

After a long time thinking, Tolik's uncle hasn't any ideas on how to solve it. But, he doesn't want to tell Tolik about his inability to solve it, so he hasn't found anything better than asking you how to solve this task.

In this task you are given a cell field n ⋅ m, consisting of n rows and m columns, where point's coordinates (x, y) mean it is situated in the x-th row and y-th column, considering numeration from one (1 ≤ x ≤ n, 1 ≤ y ≤ m). Initially, you stand in the cell (1, 1). Every move you can jump from cell (x, y), which you stand in, by any non-zero vector (dx, dy), thus you will stand in the (x+dx, y+dy) cell. Obviously, you can't leave the field, but also there is one more important condition — you're not allowed to use one vector twice. Your task is to visit each cell of the field exactly once (the initial cell is considered as already visited).

Tolik's uncle is a very respectful person. Help him to solve this task!

Input

The first and only line contains two positive integers n, m (1 ≤ n ⋅ m ≤ 10^{6}) — the number of rows and columns of the field respectively.

Output

Print "-1" (without quotes) if it is impossible to visit every cell exactly once.

Else print n ⋅ m pairs of integers, i-th from them should contain two integers x_i, y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) — cells of the field in order of visiting, so that all of them are distinct and vectors of jumps between them are distinct too.

Notice that the first cell should have (1, 1) coordinates, according to the statement.

Examples

Input


2 3


Output


1 1
1 3
1 2
2 2
2 3
2 1

Input


1 1


Output


1 1

Note

The vectors from the first example in the order of making jumps are (0, 2), (0, -1), (1, 0), (0, 1), (0, -2).
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int rows = in.nextInt();
        int cols = in.nextInt();

        List<Position> res = Solver.solve(rows, cols);
        if (res.size() <= 0) {
            out.println("-1");
        }

        for (Position pos : res) {
            out.println(pos);
        }
        out.close();
    }
}

class MaxList<E> extends ArrayList<E> {
    private int limit;

    public MaxList(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E e) {
        if (size() < limit) {
            return super.add(e);
        }
        return true;
    }
}

class Solver {
    public static List<Position> solve(int rows, int cols) {
        List<Position> res = new MaxList<Position>(rows * cols);

        Position start = new Position(1, 1);
        Position dest = new Position(rows, cols);

        while (res.size() < rows * cols) {
            CornerTracer tracerStart = new ColFirstCornerTracer(start, dest);
            CornerTracer tracerDest = new ColFirstCornerTracer(dest, start);
            drawContour(tracerStart, tracerDest, res);

            shrinkContour(start, dest);
        }
        return res;
    }

    private static void drawContour(CornerTracer first, CornerTracer second, List<Position> res) {
        if (first.done()) {
            res.add(first.getPos());
        }
        if (second.done() && !first.getPos().equals(second.getPos())) {
            res.add(second.getPos());
        }

        while (!first.done() && !second.done()) {
            res.add(first.getPos());
            res.add(second.getPos());

            first.advance();
            second.advance();
        }
    }

    private static void shrinkContour(Position start, Position dest) {
        Position newStart = new Position(dest);
        Position newDest = new Position(start);

        newStart.row += (int)Math.signum(start.row - newStart.row);
        newStart.col += (int)Math.signum(start.col - newStart.col);

        newDest.row += (int)Math.signum(dest.row - newDest.row);
        newDest.col += (int)Math.signum(dest.col - newDest.col);

        start.row = newStart.row;
        start.col = newStart.col;

        dest.row = newDest.row;
        dest.col = newDest.col;
    }
}

interface Tracer {
    public Position getPos();
    public boolean done();
    public void advance();
}

abstract class CornerTracer implements Tracer {
    protected Position curr;
    protected Position dest;

    public CornerTracer(Position start, Position dest) {
        this.curr = new Position(start);
        this.dest = new Position(dest);
    }

    @Override
    public Position getPos() {
        return new Position(curr);
    }

    @Override
    public boolean done() {
        return curr.equals(dest);
    }

    @Override
    public abstract void advance();

    public void advanceRow() {
        curr.row += (int)Math.signum(dest.row - curr.row);
    }

    public void advanceCol() {
        curr.col += (int)Math.signum(dest.col - curr.col);
    }
}

class RowFirstCornerTracer extends CornerTracer {
    public RowFirstCornerTracer(Position start, Position dest) {
        super(start, dest);
    }

    @Override
    public void advance() {
        if (curr.row != dest.row) {
            advanceRow();
        } else {
            advanceCol();
        }
    }
}

class ColFirstCornerTracer extends CornerTracer {
    public ColFirstCornerTracer(Position start, Position dest) {
        super(start, dest);
    }

    @Override
    public void advance() {
        if (curr.col != dest.col) {
            advanceCol();
        } else {
            advanceRow();
        }
    }
}

class Position {
    public int row;
    public int col;

    public Position() {
        this(0, 0);
    }

    public Position(Position other) {
        this(other.row, other.col);
    }

    public Position(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public String toString() {
        return row + " " + col;
    }

    @Override
    public boolean equals(Object other) {
        if (other == null || !(other instanceof Position)) {
            return false;
        }

        Position otherPos = (Position)other;
        return row == otherPos.row && col == otherPos.col;
    }
}
