You are given integers n and k. Your goal is to pick n distinct integer points on the xy-plane such that for exactly k pairs of points, the Euclidean distance between the points is an integer. Recall that the Euclidean distance between points (x_1, y_1) and (x_2, y_2) is \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.

It can be shown that a solution always exists under the constraints of this task.

Input

The only line contains two integers, n and k.

Output

Print n lines with the ith line containing two integers: the x and y coordinates of the ith point. The absolute value of every coordinate must be at most 10^9.

If there are multiple solutions, you can print any of them.

Constraints

• 1 \le n \le 100
• 0 \le k \le n(n - 1) / 2

Example

Input:

3 2

Output:

1 1
1 2
2 2

Explanation: The Euclidean distance between (1, 1) and (1, 2) is 1. The distance between (1, 2) and (2, 2) is also 1. However, the distance between (1, 1) and (2, 2) is \sqrt 2, which is not an integer.

Scoring