I1. Longest Increasing Path (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version the second test is $$$n=100\,000$$$. Hacks are not allowed in this problem.

Let's call an integer sequence $$$a_1, a_2, \ldots, a_n$$$ distance-convex if $$$|a_{i} - a_{i-1}| \lt |a_{i+1} - a_{i}|$$$ for every $$$1 \lt i \lt n$$$. In other words, if you jump through the points $$$a_1, a_2, \ldots, a_n$$$ on the number line in this order, each next jump is strictly longer than the previous one.

You are given two integers $$$n$$$ and $$$m$$$. Find a distance-convex sequence $$$a$$$ of length $$$n$$$ that contains at most $$$m$$$ distinct values. In terms of the jump sequence, that would mean that you need to make $$$(n-1)$$$ jumps of increasing lengths while visiting at most $$$m$$$ distinct points. $$$-10^{18} \le a_i \le 10^{18}$$$ should hold for all $$$1 \le i \le n$$$.

Input

Input consists of two integers $$$n$$$ and $$$m$$$ on a single line.

There are only 2 tests for this problem.

  • $$$n = 8$$$, $$$m = 6$$$;
  • $$$n = 100\,000$$$, $$$m = 15\,000$$$.
It is guaranteed that an answer exists for both tests.

Hacks are not allowed in this problem.

Output

Print a distance-convex sequence $$$a_1, a_2, \ldots, a_n$$$ that contains at most $$$m$$$ distinct values. $$$-10^{18} \le a_i \le 10^{18}$$$ should hold for all $$$1 \le i \le n$$$.

If there are multiple solutions, print any of them.

Example
Input
8 6
Output
1 1 3 6 10 3 11 1
Note

The sequence $$$[1, 1, 3, 6, 10, 3, 11, 1]$$$ has length $$$n=8$$$ and contains $$$5$$$ different values, which is less than or equal to $$$m=6$$$. The differences between consecutive values are $$$0,2,3,4,7,8,10$$$, a strictly increasing sequence.

$$$[1, 1, 2, 4, 8, 16, 32, 1]$$$ would be another valid answer.