Bé An vừa mới mua một con quay, và chơi trong một tiếng đồng hồ. Bỗng, bé nghĩ ra một ý tưởng thật (không) lạ, đó là một bảng lốc xoáy.

Bảng này gồm có \(m\) hàng và \(n\) cột. Chúng ta điền số \(1\) từ góc trái trên, sau đó điền lần lượt từ ngoài vào trong theo chiều kim đồng hồ. Có thể xem hình dưới để tham khảo.

Bé An muốn biết số nhỏ nhất và số lớn nhất của từng hàng. Các bạn hãy giúp An nhé!

Input

• Gồm 2 số lần lượt là \(m, n\).

Output

• Gồm \(m\) dòng, dòng thứ \(i\) in ra hai số, lần lượt là số nhỏ nhất và lớn nhất của hàng thứ \(i\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(m,n \le 10^3\)
• Subtask \(2\) (\(40\%\) số điểm): \(m,n \le 10^6\)

Example

5 6

1 6
7 22
8 30
9 27
10 15