King-Dreams-I (Intuit India)

Arrange tanks of types 1..m into a sequence of length n so that the number of contiguous subarrays containing only distinct types is maximized; if there are multiple such sequences, output the lexicographically smallest one.

输入格式

The input is n m, 1≤n≤100000, 1≤m≤10000000. Output n integers separated by spaces.

输出格式

Output the answer as described; for array answers, separate the values with spaces.

样例 1

输入：

1 2

输出：

1

样例 2

输入：

2 1

输出：

1 1

样例 3

输入：

2 2

输出：

1 2

样例说明

Construct by cycling 1,2,…,m.

Correctness: each interval of length at most m contributes at most one qualifying subarray, and an interval longer than m cannot have all distinct elements; the upper bound is Σ(n−ℓ+1), ℓ=1..min(n,m). The cyclic sequence makes every window of length ≤m consist of distinct elements, reaching this bound. A lexicographically smallest construction must always choose the smallest type that does not appear in the previous m−1 positions, so it is exactly the cycle 1,2,…,m.

Complexity: O(n) time and O(1) auxiliary space (excluding the output).