Codeforces Round 185 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

implementation

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. The Closest Pair

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputCurrently Tiny is learning Computational Geometry. When trying to solve a problem called "The Closest Pair Of Points In The Plane", he found that a code which gave a wrong time complexity got Accepted instead of Time Limit Exceeded.

The problem is the follows. Given *n* points in the plane, find a pair of points between which the distance is minimized. Distance between (*x*_{1}, *y*_{1}) and (*x*_{2}, *y*_{2}) is .

The pseudo code of the unexpected code is as follows:

input n

for i from 1 to n

input the i-th point's coordinates into p[i]

sort array p[] by increasing of x coordinate first and increasing of y coordinate second

d=INF //here INF is a number big enough

tot=0

for i from 1 to n

for j from (i+1) to n

++tot

if (p[j].x-p[i].x>=d) then break //notice that "break" is only to be

//out of the loop "for j"

d=min(d,distance(p[i],p[j]))

output d

Here, *tot* can be regarded as the running time of the code. Due to the fact that a computer can only run a limited number of operations per second, *tot* should not be more than *k* in order not to get Time Limit Exceeded.

You are a great hacker. Would you please help Tiny generate a test data and let the code get Time Limit Exceeded?

Input

A single line which contains two space-separated integers *n* and *k* (2 ≤ *n* ≤ 2000, 1 ≤ *k* ≤ 10^{9}).

Output

If there doesn't exist such a data which let the given code get TLE, print "no solution" (without quotes); else print *n* lines, and the *i*-th line contains two integers *x*_{i}, *y*_{i} (|*x*_{i}|, |*y*_{i}| ≤ 10^{9}) representing the coordinates of the *i*-th point.

The conditions below must be held:

- All the points must be distinct.
- |
*x*_{i}|, |*y*_{i}| ≤ 10^{9}. - After running the given code, the value of
*tot*should be larger than*k*.

Examples

Input

4 3

Output

0 0

0 1

1 0

1 1

Input

2 100

Output

no solution

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/08/2023 22:11:18 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|