座位

本题选手包（附加文件）为 7z AES-256 加密，解压密码：p68992F82QkHytbzhgNb

题目描述

铁四角报告厅有一排 $n$ 个座位，从左到右编号为 $1$ 到 $n$。今天有 $m$ 位观众依次入场，每人会挑一个空座位坐下。

观众挑座位的规则如下：

• 第一位观众没有参照物，直接坐在 $1$ 号座位上；
• 之后每一位观众，先对每个空座位算出舒适度：该座位到所有已经坐下的人的距离中的最小值；
• 然后在所有空座位中选择舒适度最大的那个；
• 如果有多个座位的舒适度并列最大，选择编号最小的那个。

两名观众之间的距离，指他们座位编号之差的绝对值。形式化地说，若第 $i$ 位观众坐下后已占座位的集合为 $S_i$，则对空座位 $x$ 定义其舒适度为 $d(x)=\min_{y\in S_i}\lvert x-y\rvert$。

第 $i+1$ 位观众选择的座位，就是使 $d(x)$ 取得最大值的空座位；若同时有多个座位取到最大值，选择编号最小的那一个。

请你按入场顺序输出每位观众坐下的座位编号。

输入格式

从文件 seat.in 中读入数据。

输入一行两个正整数 $n$ 和 $m$，分别表示座位数与观众数。

输出格式

输出到文件 seat.out 中。

输出一行 $m$ 个正整数，第 $i$ 个数表示第 $i$ 位观众坐下的座位编号。

样例 1 输入

5 3

样例 1 输出

1 5 3

样例 1 解释

第 1 位观众坐 1 号座位。

第 2 位观众看空座位 $2,3,4,5$，它们到 1 号的距离分别是 $1,2,3,4$，舒适度最大的是 5 号。

第 3 位观众看空座位 $2,3,4$，它们到已坐的 1 号与 5 号的最小距离分别是 $1,2,1$，舒适度最大的是 3 号。

样例 2 输入

6 4

样例 2 输出

1 6 3 2

样例 2 解释

第 1 位坐 1 号；第 2 位到 1 号最远，坐 6 号；第 3 位在空位 $2,3,4,5$ 中，到 1 号与 6 号的最小距离分别是 $1,2,2,1$，取编号小的 3 号；第 4 位在空位 $2,4,5$ 中最小距离分别是 $1,1,1$，并列时取编号最小的 2 号。所以答案是 $1,6,3,2$。

样例 3

见选手目录下的 seat/seat3.in 与 seat/seat3.ans。

该样例满足测试点 $1\sim 3$ 的约束条件。

样例 4

见选手目录下的 seat/seat4.in 与 seat/seat4.ans。

该样例满足测试点 $18\sim 22$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le m\le n\le 5000$。

特殊性质 A：保证每次挑选时不会出现并列。

特殊性质 B：$m\le\lceil n/2\rceil$。

特殊性质 C：$m\le n/2$，且每一位观众都坐在当前编号最小或最大的空座位上。