Hamiltonian path P28992

Recall that a Hamiltonian path of a directed graph is one that visits every vertex exactly once. Most computer scientists believe that no such path can be computed efficiently. Your task here is to prove that they are wrong. Well, more or less...

Let n be the number of vertices of the graph. For every pair of vertices x and y, with x < y, there is exactly one arc connecting them, either from x to y or from y to x. We will use a constant k to decide the direction of each arc. Compute r = (k + x)(k − x)(k + y)(k − y), and let d be the central digit of r (the one to the right, if r has an even number of digits). Then, if d is odd, the arc goes from x to y. Otherwise, the arc goes from y to x.

For instance, if k = 4, x = 1 and y = 2, then r = 5 · 3 · 6 · 2 = 180. Since 8 is even, the arc goes from 2 to 1. As another example, if k = 21, x = 2 and y = 3, then r = 23 · 19 · 24 · 18 = 188784. Since 7 is odd, the arc goes from 2 to 3.

Given n and the constant k that implicitly defines the arcs of the graph, can you find a Hamiltonian path?

Input

Input consists of several cases, each one with n and k. Assume 2 ≤ n ≤ 10⁴, n < k ≤ 3 · 10⁴, and that vertices are numbered starting at one.

Output

For every case, print a line with a Hamiltonian path of the implicit graph. The path can start and end at any vertices. If there is more than one solution, print any of them. If there is no solution, print “weird things happen”.

Observations

• The definition of r is only meant to be pseudo-random.
• Be aware that you need long longs to compute r.