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 một dòng duy nhất chứa hai số nguyên dương \(m\) và \(n\) \((1 \leq m, n \leq 10^{6})\).

Output

• In ra \(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 \leq 10^{3}\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5 6

1 6
7 22
8 30
9 27
10 15