There are N platforms in front of Jie Feng numbered 1 to N. Platform i is at height i metres from the ground.
Jie Feng wants to visit each platform exactly once. To do so, Jie Feng needs to make (N - 1) jumps between the platforms.
As it is dangerous for Jie Feng to make jumps where the difference in height is large, he has a jetpack to help him.
Before making any jump, in order to operate the jetpack, Jie Feng has to first input K distinct integers into the jetpack: the jump heights that the jetpack is allowed to operate on.
Jie Feng can only jump between two platforms if the absolute difference in their heights is one of the K integers Jie Feng has entered in the jetpack.
Moreover, to avoid damaging the jets in his jetpack, Jie Feng has to ensure that he utilizes every jump height at least once. This means that each of the K jump heights must be equal to the height difference between two platforms of at least one of the (N - 1) jumps Jie Feng makes.
Help Jie Feng to find any valid order to visit the platforms, and the K jump heights Jie Feng inputs for the order that you have found. It is guaranteed that there is at least one valid way to visit the platforms.
The only line of input contains two integers, N, the number of platforms, and K, the number of jumps heights Jie Feng needs to input.
On the first line, output K integers, the jump heights that Jie Feng needs to input into the jetpack.
On the following line, output N integers. The ith integer should indicate the ith platform that Jie Feng should visit.
Subtask 1 (12%): 2 ≤ N ≤ 1 000 000. K = 1.
Subtask 1 (14%): 3 ≤ N ≤ 1 000 000. K = 2.
Subtask 3 (14%): 1 ≤ K < N ≤ 4.
Subtask 4 (19%): 1 ≤ K < N ≤ 11.
Subtask 5 (41%): 1 ≤ K < N ≤ 1 000 000.
Subtask 6 (0%): Sample Testcases
Sample Testcase 1
2 4 6 1 3 5