Hide

Problem I
Special Tour

/problems/specialtour/file/statement/en/img-0001.png
Given an grid with $N$ rows and $M$ columns, your task is to find a tour such that:
  1. The tour has length at least two

  2. All squares in the grid are visited exactly once

  3. Let $a_1, \dots , a_{NM}$ be the sequence of visited squares. Then $d(a_ k$, $a_{k+1}) = 2$ or $3$ for every $1 \leq k < NM$. Also, $d(a_{NM}, a_1) = 2$ or $3$.

    Here, $d(p, q)$ denotes the Manhattan distance between $p$ and $q$. More precisely, if $p$ is the square on row $r_ p$ and column $c_ p$ and $q$ is the square on row $r_ q$ and column $c_ q$, then we write $p = (r_ p, c_ p), q = (r_ q, c_ q)$ and $d(p, q) = |r_ p - r_ q| + |c_ p - c_ q|$.

Input

The first and only line of input consists of two integers $N$ and $M$ ($1 \leq N, M \leq 200$).

Output

If there is no such tour, output -1. Otherwise, output $N \times M$ lines. The $i$th line contains two space-separated integers, denoting the row and column numbers of $a_ i$. If there is more than one such tour, any one will be accepted.

Sample Input 1 Sample Output 1
2 3
1 1
2 2
1 3
2 1
1 2
2 3
Sample Input 2 Sample Output 2
1 1
-1

Please log in to submit a solution to this problem

Log in