M6

Cerință

Metroul de pe M6 are $N$ scaune așezate în linie și numerotate de la $1$ la $N$. Pentru că utilizatorii acestei linii sunt disciplinați, aceștia vor intra câte unul pe rând în acest metrou. Atunci când un pasager intră în metrou și vrea să se așeze, întotdeauna va alege scaunul cu distanța maximă față de cel mai apropiat vecin. Dacă există mai multe astfel de scaune, se va alege cel cu indicele minim.

Spre exemplu, dacă avem un metrou cu $10$ scaune iar în metrou intră $6$ pasageri, ei se vor așeza pe scaune în felul următor:

• Primul pasager se va așeza pe scaunul $1$;
• Al doilea pasager se va așeza pe scaunul $10$;
• Al treilea pasager se poate așeza fie pe scaunul $5$, fie pe $6$ (acestea sunt cele mai depărtate scaune de unele deja ocupate), dar îl va alege pe $5$, deoarece are indicele mai mic;
• Al patrulea pasager se va așeza pe scaunul $3$. Atenție: acesta nu se așează pe scaunul $7$, deoarece se ia distanța minimă față de vecini, iar aceasta ar fi tot $2$;
• Al cincilea pasager se va așeza pe scaunul $7$;
• Al șaselea pasager se va așeza pe scaunul $2$.

Dorim să aflăm pentru $M$ pasageri care intră pe rând în metrou, pe ce scaun se va așeza fiecare.

Date de intrare

Pe prima linie se vor afla numerele naturale $N$ și $M$, cu specificația din enunț.

Date de ieșire

Pe prima linie se vor afișa $M$ numere separate prin spațiu. Al $i$-lea număr va reprezenta scaunul pe care se așează cel de-al $i$-lea pasager.

Restricții și precizări

• $1 \leq M \leq 2 \cdot 10^5$;
• $1 \leq N \leq 10^9$;
• Se garantează că $M \leq N$ pentru toate testele;
• Pentru $20\%$ din punctaj, $M, N \leq 50$;
• Pentru $60\%$ din punctaj, $M \leq 1000, N \leq 10^9$;
• Pentru restul testelor, nu există restricții suplimentare.

Exemplul 1

stdin

10 6

stdout

1 10 5 3 7 2

Exemplul 2

stdin

16 10

stdout

1 16 8 12 4 6 10 14 2 3