In Finite Encyclopedia of Integer Sequences (FEIS), all integer sequences of lengths between 1 and N (inclusive) consisting of integers between 1 and K (inclusive) are listed.
Let the total number of sequences listed in FEIS be X. Among those sequences, find the (X/2)-th (rounded up to the nearest integer) lexicographically smallest one.

-----Constraints-----
 - 1 \leq N,K \leq 3 × 10^5
 - N and K are integers.

-----Input-----
Input is given from Standard Input in the following format:
K N

-----Output-----
Print the (X/2)-th (rounded up to the nearest integer) lexicographically smallest sequence listed in FEIS, with spaces in between, where X is the total number of sequences listed in FEIS.

-----Sample Input-----
3 2

-----Sample Output-----
2 1 

There are 12 sequences listed in FEIS: (1),(1,1),(1,2),(1,3),(2),(2,1),(2,2),(2,3),(3),(3,1),(3,2),(3,3).
The (12/2 = 6)-th lexicographically smallest one among them is (2,1).

Difficulty: competition

Starter code:

Solutions:
k,n = map(int,input().split())
if k %2 ==0:
  ans = []
  ans.append(k//2)
  for i in range(n-1):
    ans.append(k)
  print(*ans)
else:
  ans = []
  for i in range(n):
    ans.append(k//2+1)
  sage = (n)//2
  for i in range(sage):
    if ans[-1] == 1:
      ans.pop()
    else:
      ans[-1] -= 1
      while len(ans) < n:
        ans.append(k)
  print(*ans)

#!/usr/bin/env python3

import math

def main():
    [K, N] = list(map(int, input().split()))

    r = []
    if K == 1:
        r = [1] * ((N + 1) // 2)
    elif K % 2 == 0:
        r = [K // 2]
        r += [K] * (N - 1)
    else:
        t = N // 2
        x = int(math.log(N * (K - 1) + 1, K) - 1)
        while t < ((K ** (x + 1) - 1) / (K - 1) + x) // 2:
            x -= 1
        x += 1
        r = [(K + 1) // 2] * (N - x)
        r += [0] * x
        t = ((K ** (x + 1) - 1) / (K - 1) + x) // 2 - t
        for i in range(x, 0, -1):
            r[N - i] = 1
            t -= 1
            for j in range(K - 1):
                if t == 0:
                    break
                if K ** i - 1 <= t * (K - 1):
                    r[N - i] += 1
                    t -= (K ** i - 1) // (K - 1)
            if t == 0:
                break

        for i in range(len(r) - 1, -1, -1):
            if r[i] == 0:
                r.pop()
            else:
                break


    print((' '.join(list(map(str, r)))))


def __starting_point():
    main()


__starting_point()

from itertools import chain,repeat
K,N = list(map(int,input().split()))

def solve():

  if K % 2 == 0:
    return ' '.join(map(str, chain((K//2,),repeat(K,N-1))))
  else:
    seq = [K//2+1]*N
    d = N//2
    for _ in range(d):
      if seq[-1] == 1:
        seq.pop()
      else:
        seq[-1] -= 1
        seq.extend(repeat(K,N-len(seq)))
    return ' '.join(map(str, seq))

def naive():
  from itertools import product
  s = sorted(chain.from_iterable(product(list(range(1,K+1)),repeat=i) for i in range(1,N+1)))
  return ' '.join(map(str, s[(len(s)-1)//2]))

print((solve()))
# print(naive())


K, N = list(map(int, input().split()))

if K % 2 == 0:
    ans = [K//2] + [K] * (N-1)
else:
    ans = [(K+1)//2] * N
    for i in range(N//2):
        if ans[-1] == 1:
            ans.pop()
        else:
            ans[-1] -= 1
            ans += [K] * (N - len(ans))

print((' '.join(map(str, ans))))


def solve(k, n):
    if k & 1 == 0:
        return [k // 2] + [k] * (n - 1)
    ans = [k // 2 + 1] * n
    l = n
    for i in range((n - 2) // 2 + 1):
        if ans[-1] == 1:
            ans.pop()
            l -= 1
        else:
            ans[-1] -= 1
            if l < n:
                ans += [k] * (n - l)
                l = n
    return ans


k, n = list(map(int, input().split()))

print((*solve(k, n)))


def main():
    K,N = map(int,input().split())

    if K % 2 == 0:
        ans = [K//2]
        for i in range(N-1):
            ans.append(K)
    else:
        back = N // 2
        mid = K // 2 + 1
        ans = [mid for i in range(N)]
        for i in range(back):
            if ans[-1] == 1:
                ans.pop()
            else:
                ans[-1] -= 1
                while len(ans) < N:
                    ans.append(K)
    print(' '.join(map(str, ans)))

def __starting_point():
    main()
__starting_point()

import sys
readline = sys.stdin.readline

INF = 10**9+7
def calc(n, k):
    if k == 1:
        return n
    if n > 20:
        return INF
    return min(INF, (pow(k, n)-1)//(k-1))
    

K, N = list(map(int, readline().split()))

if K%2 == 0:
    ans = [K//2] + [K]*(N-1)
    print((*ans))
else:    
    ans = []
    cnt = 0
    half = True
    for l in range(N, 0, -1):
        clk = calc(l, K)
        if half:
            c = 1+K//2
            if l%2 == 0:
                cnt += 1
            if clk//2 == cnt:
                ans.append(c)
                break
            if clk//2 < cnt:
                c -= 1
                half = False
                cnt -= clk//2 + 1
                
                while cnt >= clk:
                    cnt -= clk
                    c -= 1
                if cnt == clk-1:
                    ans.append(c)
                    break
        else:
            c = K
            while cnt >= clk:
                    cnt -= clk
                    c -= 1
            if cnt == clk-1:
                ans.append(c)
                break
        ans.append(c)
    print((*ans))


# seishin.py
K, N = list(map(int, input().split()))
if K % 2 == 0:
    print((*[K//2] + [K]*(N-1)))
else:
    X = [(K+1)//2] * N
    for i in range(N//2):
        if X[-1] == 1:
            X.pop()
        else:
            X[-1] -= 1
            X.extend([K]*(N-len(X)))
    print((*X))


K,N = list(map(int,input().split()))
if K % 2 == 0:
    ans = [K//2]
    for i in range(N-1):
        ans.append(K)
else:
    back = N//2
    mid = K//2 + 1
    ans = [mid for i in range(N)]
    for i in range(back):
        if ans[-1] == 1:
            ans.pop()
        else:
            ans[-1] -= 1
            while len(ans) < N:
                ans.append(K)
print((' '.join(map(str,ans))))


import sys
input = sys.stdin.readline

K,N = map(int,input().split())

if K % 2 == 0:
    L = K // 2
    R = L + 1
    # 先頭の文字が L のものの最後、R のものの最初、で境界
    arr = [L] + [K] * (N-1)
else:
    """
    [3,3,3,3,3] だと 手前に3 33 333 3333 が余分。2歩戻る。
    """
    arr = [(K+1)//2] * N
    x = N//2# x歩 戻る
    for i in range(x):
        arr[-1] -= 1
        if arr[-1] == 0:
            arr.pop()
            continue
        L = len(arr)
        if L < N:
            arr += [K] * (N-L)

answer = ' '.join(map(str,arr))
print(answer)

import math


def main(K, N):
    ans = []

    if K % 2 == 0:
        for i in range(N):
            if i == 0:
                ans.append(K // 2)
            else:
                ans.append(K)
    elif K == 1:
        n2 = math.ceil(N / 2)
        for i in range(n2):
            ans.append(1)
    else:
        K2 = math.ceil(K / 2)
        ans = [K2] * N
        n = N // 2
        for i in range(n):
            if ans[-1] == 1:
                ans.pop()
            else:
                ans[-1] -= 1
                while len(ans) < N:
                    ans.append(K)

    return ' '.join(map(str, ans))


K, N = list(map(int, input().split()))
print((main(K, N)))


a,n=map(int,input().split())
if a%2==0:
    print(*[a//2]+[a]*(n-1))
else:
    d=[(a+1)//2]*n
    for i in range(n//2):
        if d[-1]==1:
            d.pop()
        else:
            d[-1]-=1
            d.extend([a]*(n-len(d)))
    print(" ".join(str(i)for i in d))

k, n = map(int, input().split())
if k % 2 == 0:
    print(k // 2, end=" ")
    for i in range(n - 1):
        print(k, end=" ")
else:
    l = [(k + 1) // 2 for i in range(n)]
    for i in range(n // 2):
        if l[-1] == 1:
            l.pop()
        else:
            l[-1] -= 1
            for j in range(n - len(l)):
                l.append(k)
    print(*l, sep=" ")

k,n = map(int,input().split())
if k%2 == 0:
  ans = [k//2]+[k]*(n-1)
else:
  t = n//2
  ans = [k//2+1]*n
  for i in range(t):
    if ans[-1] == 1:
      ans.pop()
    else:
      ans[-1] -= 1
      while len(ans) < n:
        ans.append(k)
print(*ans)

import sys
sys.setrecursionlimit(10**6)
k, n = map(int, input().split())

def calc_x(K, N):
	return (pow(K, N+1)-K) // (K-1)
def lexico(K, N, X):
	#print(K, N, X)
	nonlocal ans
	if X == 0:
		return
	q = (calc_x(K, N-1)+1)
	if N > 1:
		ans.append((X//q) + 1)
	else:
		ans.append((X//q))
	lexico(K, N-1, (X-1)%q)

if k == 1:
	print(*[1 for _ in range((n+1)//2)])
elif n == 1:
	print((k+1)//2)
elif k%2 == 0:
	ans = [k//2] + [k] * (n-1)
	print(*ans)
else:
	if n%2 == 1:
		cur, i = 1, n
	else:
		cur, i = 0, n
	while cur <= i:
		i -= 1
		cur += pow(k, n-i)
	ans = [(k+1)//2] * i
	ind = (cur-i) // 2
	lexico(k, n-i, ind)
	print(*ans)

K, N = map(int, input().split())
if K % 2 == 0:
  print(K // 2, end = ' ')
  for i in range(1, N):
    if i != N - 1:
      print(K, end = ' ')
    else:
      print(K)
else:
  def superlist(L, n):
    if n % 2 == 1:
      return [L // 2 + 1] + superlist(L, n-1)
    else:
      Ax = [L // 2 + 1 for i in range(n)]
      j = n - 1
      for i in range(n // 2):
        Ax[j] -= 1
        if Ax[j] == 0:
          j -= 1
        else:
          for m in range(j + 1, n):
            Ax[m] = L
          j = n - 1
      return Ax
  if K == 1:
    for i in range((N - 1) // 2 + 1):
      if i != (N - 1) // 2:
        print(1, end = ' ')
      else:
        print(1)
  else:
    A = superlist(K, N)
    for _ in range(N):
      if _ != N - 1 and A[_] != 0:
        print(A[_], end = ' ')
      elif _ == N - 1 and A[_] != 0:
        print(A[_])

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    k,n=MI()
    end = n - 1
    if k%2:
        ans=[k//2+1]*n
        for _ in range(n//2):
            if ans[end]==1:
                end-=1
            else:
                ans[end]-=1
                if end!=n-1:
                    for i in range(end+1,n):
                        ans[i]=k
                    end=n-1
    else:
        ans=[k//2]+[k]*(n-1)
    print(*ans[:end+1])

main()

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline
sys.setrecursionlimit(10**5)

k,n = list(map(int, read().split()))

if k%2==0:
    print((*([k//2]+[k]*(n-1))))
    return

if k==1:
    print((*[1]*((n+1)//2)))
    return

ans = [(k+1)//2]*n
d = 0
def f(k,i,d):
    # d <= 1+k+...+k^i?
    v = 1
    for j in range(i):
        v *= k
        v += 1
        if v > d: return True
    return False

def g(k,i):
    # 1+k+...+k^i
    v = 1
    for j in range(i):
        v *= k
        v += 1
    return v
    
for i in range(1,n):
    if f(k,n-i-1,d):
        d += 1
        continue
    """
    以下　300000 >= d >= 1+k+...+k^(n-i-1)
    i 番目の項から真ん中にならない    
    v 番目を目指す
    """
    v = (g(k,n-i)+d+1)//2 - d - 1
    
    for j in range(i,n):
        #print(v)
        if v==0:
            ans[j] = 0
            continue

        p = g(k,n-j-1)
        q = (v-1)//p 
        #print(v,j,p,q)
        
        ans[j] = q+1
        v -= 1+q*p        



    
    break


while ans[-1]==0:
    ans.pop()
print((*ans))









N,K=map(int,input().split())
#1 2 3...N
if N%2==0:
  L=[str(N)]*K
  L[0]=str(N//2)
  print(" ".join(L))
  return
#L[0]=N//2+1
#N//2のずれ？
L=[(N//2)+1]*K
for i in range(K//2):
  if L[-1]==1:
    L.pop(-1)
  elif len(L)!=K:
    L[-1]-=1
    L+=[N]*(K-len(L))
  else:
    L[-1]-=1
L=list(map(str,L))
print(" ".join(L))