Keyence Programming Contest 2020 - Subarray Sum

Given are three integers N, K, and S.

Find a sequence A_1, A_2, ..., A_N of N integers between 1 and 10^9 (inclusive) that satisfies the condition below. We can prove that, under the conditions in Constraints, such a sequence always exists.

* There are exactly K pairs (l, r) of integers such that 1 \leq l \leq r \leq N and A_l + A_{l + 1} + \cdots + A_r = S.

Constraints

* 1 \leq N \leq 10^5
* 0 \leq K \leq N
* 1 \leq S \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K S


Output

Print a sequence satisfying the condition, in the following format:


A_1 A_2 ... A_N

Output

Print a sequence satisfying the condition, in the following format:


A_1 A_2 ... A_N

Examples

Input

4 2 3


Output

1 2 3 4


Input

5 3 100


Output

50 50 50 30 70

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(n, k, s) = map(int, input().split())
if s == 10 ** 9:
	ans = [10 ** 9] * k + [1] * (n - k)
else:
	ans = [s] * k + [s + 1] * (n - k)
print(*ans)


(n, k, s) = map(int, input().split())
o = [s + 1] * n
if s == 10 ** 9:
	o = [1] * n
for i in range(k):
	o[i] = s
print(*o)


(n, k, s) = map(int, input().split())
print(*[s] * k + [7] * (n - k))


(N, K, S) = map(int, input().split())
ans = [S] * N
m = 10 ** 9
for i in range(N - K):
	ans[i] %= m
	ans[i] += 1
print(*ans)


(N, K, S) = map(int, input().split())
for i in range(N):
	if i <= K - 1:
		print(S, end=' ')
	else:
		print(96517, end=' ')


(n, k, s) = map(int, input().split())
a = [s] * k
if s != 10 ** 9:
	a += [10 ** 9] * (n - k)
	print(*a)
else:
	b = [10 ** 9] * k + [1] * (n - k)
	print(*b)


(N, K, S) = map(int, input().split())
if S == 10 ** 9:
	A = [S] * K + [S - 1] * (N - K)
else:
	A = [S] * K + [S + 1] * (N - K)
print(*A)


(n, k, s) = map(int, input().split())
padding = (s + 1) % 10 ** 9
ans = [s] * k + [padding] * (n - k)
print(' '.join(map(str, ans)))


(n, k, s) = map(int, input().split())
l = [s] * k
if s == 1:
	l += [s + 1] * (n - k)
else:
	l += [s - 1] * (n - k)
print(*l)


(N, K, S) = map(int, input().split())
m = 1
a = [S] * K + [S // 2 + 3] * (N - K)
print(' '.join([str(i) for i in a]))


(a, b, c) = list(map(int, input().split()))
p = 1
x = [c] * a
while c % p == 0:
	p = p + 1
for i in range(b, a):
	x[i] = p
print(*x)


(N, K, S) = map(int, input().split())
if S == 10 ** 9:
	ans = [S - 1] * N
else:
	ans = [10 ** 9] * N
for i in range(K):
	ans[i] = S
print(*ans)


(n, k, s) = [int(x) for x in input().split()]
if s == 10 ** 9:
	l = [1] * (n - k) + [s] * k
else:
	l = [s + 1] * (n - k) + [s] * k
print(*l)


(N, K, S) = map(int, input().split())
cur = 1 if S == 10 ** 9 else S + 1
ans = [S] * K + [cur] * (N - K)
print(*ans)


(N, K, S) = map(int, input().split())
ans = [S] * K
e = S + 1 if S < 10 ** 9 else S - 1
for _ in range(K, N):
	ans.append(e)
print(*ans)


(N, K, S) = map(int, input().split())
X = [26845184 for _ in range(N)]
ans = ''
for i in range(K):
	X[i] = S
print(*X)


(n, k, s) = map(int, input().split())
A = [1 * 10 ** 9 if s != 1 * 10 ** 9 else 1 for i in range(n)]
for i in range(k):
	A[i] = s
print(*A)


(n, k, s) = map(int, input().split())
x = 10 ** 9
if s == x:
	x = 1
a = [s] * k + [x] * (n - k)
print(*a)


x = 10 ** 9 - 7
(n, k, s) = map(int, input().split())
ls_a = [s] * k
ls_b = [x] * (n - k)
print(' '.join(list(map(str, ls_a + ls_b))))


(n, k, s) = map(int, input().split())
num = 998245637
arr = [s] * k
arr2 = [num] * (n - k)
print(*arr + arr2)


(N, K, S) = map(int, input().split())
T = S + 1
if S + 1 > 100:
	T = S - 1
ans = [S] * K + [T] * (N - K)
print(*ans)


(N, K, S) = map(int, input().split())
for i in range(K):
	print(S, end=' ')
for i in range(N - K):
	print(10 ** 8 + 3234523, end=' ')


(N, K, S) = map(int, input().split())
result = [S % 10 ** 9 + 1] * N
for i in range(K):
	result[i] = S
print(*result)


(n, k, s) = map(int, input().split())
l1 = [s] * k
l2 = [s + 1 if s == 1 else s - 1] * (n - k)
print(' '.join(map(str, l1 + l2)))


(N, K, S) = map(int, input().split())
ans = [S] * K
if S == 1:
	ans += [2] * (N - K)
else:
	ans += [S - 1] * (N - K)
print(*ans, sep=' ')


(n, k, s) = map(int, input().split())
for _ in range(k):
	print(s, end=' ')
for _ in range(n - k):
	print(s + 1 if s < 1000000000 else 1, end=' ')


(n, k, s) = map(int, input().split())
a = []
for i in range(k):
	a.append(s)
for j in range(n - k):
	a.append(s + 1 if s == 1 else s - 1)
print(*a)


(N, K, S) = [int(x) for x in input().split()]
if S != 10 ** 9:
	A = [S] * K + [S + 1] * (N - K)
else:
	A = [S] * K + [S - 1] * (N - K)
print(*A)


(N, K, S) = map(int, open(0).read().split())
fill = 10 ** 9 - 1 if S == 10 ** 9 else 10 ** 9
ans = [S] * K + [fill] * (N - K)
print(*ans)


(n, k, s) = map(int, input().split())
if s == 10 ** 9:
	b = ['1']
else:
	b = [str(s + 1)]
ans = [str(s)] * k + b * (n - k)
print(' '.join(ans))


(N, K, S) = [int(i) for i in input().split()]
ans = [S] * K
if S != 10 ** 9:
	n = S + 1
else:
	n = 1
ans += [n] * (N - K)
print(*ans)


(n, k, s) = map(int, input().split())
ans = [s] * k + [s % 10 ** 6 + 1 for i in range(n - k)]
print(' '.join(map(str, ans)))


(N, K, S) = map(int, input().split())
MOD = 10 ** 9
num = S + 1 if S < MOD else S - 1
ans = [S] * K + [num] * (N - K)
print(*ans)


(a, b, c) = map(int, input().split())
M = 10 ** 9
if c == M:
	l = [c] * b + [1] * (a - b)
else:
	l = [c] * b + [M] * (a - b)
print(*l)


(n, k, s) = map(int, input().split())
L = [s] * k + [min(s + 1, 10 ** 9 - 1)] * (n - k)
print(' '.join(map(str, L)))


(n, k, s) = map(int, input().split())
print(*[s] * k + [s % 10 ** 9 + 1] * (n - k))


(N, K, S) = map(int, input().split())
t = [999999999] * N
for i in range(K):
	t[i] = S
print(*t)


(N, K, S) = [int(i) for i in input().split()]
res = [10 ** 9 - 7] * N
for i in range(K):
	res[i] = S
print(*res)


(n, k, s) = map(int, input().split())
for i in range(1, n + 1):
	if i <= k:
		print(s)
	else:
		print(10 ** 7 + 5)


(n, k, s) = map(int, input().split())
ans = [s] * k + [19] * (n - k)
print(*ans)


(n, k, s) = map(int, input().split())
if s == 10 ** 9:
	res = (str(s) + ' ') * k + '1 ' * (n - k)
else:
	res = (str(s) + ' ') * k + (str(s + 1) + ' ') * (n - k)
print(res)


(N, K, S) = map(int, input().split())
S2 = S - 1 if S == 1000000000 else S + 1
As = [S] * K + [S2] * (N - K)
print(' '.join(map(str, As)))


(n, k, s) = map(int, input().split())
a = [s] * n
for i in range(k, n):
	a[i] += 1 - (s == 10 ** 9) * s
print(*a)


(n, k, s) = map(int, input().split())
ans = [0] * n
for i in range(k):
	ans[i] = s
for i in range(k, n):
	ans[i] = s + 1 - 2 * (s == 1000000000.0)
print(*ans)


(n, k, s) = map(int, input().split())
a = [s] * k
a += [9857349] * (n - k)
print(*a, sep=' ')


(N, K, S) = map(int, input().split())
A = [str(S)] * K
if S == 10 ** 9:
	B = ['1'] * (N - K)
else:
	B = [str(S + 1)] * (N - K)
ans = A + B
print(' '.join(ans))


(n, k, s) = map(int, input().split())
m = 10 ** 9
c = [s] * k + [(s + 1) % m] * (n - k)
print(*c)


(N, K, S) = map(int, input().split())
T = S + 1 if S < 10 ** 9 else S - 1
L = [S] * K + [T] * (N - K)
print(*L)


(N, K, S) = map(int, input().split())
ans = [S] * K + [[7, S + 1][S != 10 ** 9]] * (N - K)
print(*ans)


(N, K, S) = map(int, input().split())
if S > 1:
	t = S - 1
else:
	t = S + 1
print(*[S] * K + [t] * (N - K))


(N, K, S) = map(int, input().split())
i = 1
while S % i == 0:
	i += 1
print(*[S] * K + [i] * (N - K))


(n, k, s) = map(int, input().split())
a = [s] * k + [1 if n < s else s + 1] * (n - k)
print(*a)


(n, k, s) = map(int, input().split())
a = [s] * k
b = [pow(10, 9) if not s == pow(10, 9) else 1] * (n - k)
print(' '.join(map(str, a + b)))


(N, K, S) = map(int, input().split())
if S >= 3:
	print(*[S] * K + [S - 1] * (N - K))
else:
	print(*[S] * K + [S + 1] * (N - K))


(n, k, s) = map(int, input().split())
if s == 1000000000:
	x = [s] * k + [1] * (n - k)
else:
	x = [s] * k + [s + 1] * (n - k)
print(*x)


(n, k, s) = map(int, input().split())
ans = [s] * k
if s != 1:
	ans += [s - 1] * (n - k)
else:
	ans += [2] * (n - k)
print(*ans)


(N, K, S) = map(int, input().split())
l = [S] * K + [(S + 1) % 10 ** 9] * (N - K)
print(' '.join(map(str, l)))


(n, k, s) = map(int, input().split())
A = [s] * k
if s == pow(10, 9):
	A += [1] * (n - k)
else:
	A += [s + 1] * (n - k)
print(*A)


(N, K, S) = map(int, input().split())
if S > 2:
	print(*[S] * K + [S - 1] * (N - K))
else:
	print(*[S] * K + [S + 10 ** 6] * (N - K))


(N, K, S) = map(int, input().split())
if S >= 2 * 10 ** 6:
	s = 1
else:
	s = 10 ** 9
answer = [S] * K + [s] * (N - K)
print(*answer)


(N, K, S) = map(int, input().split())
ans = [S for _ in range(K)] + [(S + 1) % int(1000000000.0) for _ in range(N - K)]
print(' '.join(map(str, ans)))


(n, k, s) = [int(v) for v in input().split()]
ans = [s] * k + [998244353] * (n - k)
print(*ans)


(N, K, S) = map(int, input().split())
A = [S] * N
for i in range(K, N):
	if S == 1:
		A[i] = S + 1
	else:
		A[i] = S - 1
print(*A)


(n, k, s) = map(int, input().split())
x = s + 1 if s < 10 ** 9 else 1
a = [x] * n
for i in range(k):
	a[i] = s
print(*a, sep=' ')


(N, K, S) = map(int, input().split())
if S == 10 ** 9:
	print(*[S] * K + [1] * max(0, N - K))
else:
	print(*[S] * K + [10 ** 9] * max(0, N - K))


(N, K, S) = map(int, input().split())
A = [S] * K
A.extend([S + 1 if S < 10 ** 9 else 1] * (N - K))
print(' '.join((str(a) for a in A)))


(N, K, S) = map(int, input().split())
ans = [S] * K
if N - K >= S:
	ans.extend([S + 1] * (N - K))
else:
	ans.extend([1] * (N - K))
print(*ans)


(n, k, s) = map(int, input().split())
ans = [s] * k + [197] * (n - k)
print(*ans)


(n, k, s) = map(int, input().split())
l = [s] * k
if s == 10 ** 9:
	l.extend([1] * (n - k))
else:
	l.extend([s + 1] * (n - k))
print(*l)


(n, k, s) = map(int, input().split())
o = 10 ** 9
if s == 10 ** 9:
	o = 1
res = [s] * k + [o] * (n - k)
print(*res)


(n, k, s) = map(int, input().split())
if s == 1:
	ans = [2] * n
else:
	ans = [s - 1] * n
for i in range(k):
	ans[i] = s
print(*ans)


(n, k, s) = map(int, input().split())
print(*[s] * k + [9 ** 9] * (n - k))


(N, K, S) = map(int, input().split())
rem = 1 if S >= 10 ** 9 else S + 1
ret = [S] * K + [rem] * (N - K)
print(' '.join(map(str, ret)))


(N, K, S) = map(int, input().split())
if S < 10 ** 9:
	T = S + 1
else:
	T = S - 1
U = [S] * K + [T] * (N - K)
print(' '.join(map(str, U)))


(N, K, S) = list(map(int, input().split()))
L = [0] * N
L[:K] = [S] * K
if S == 10 ** 9:
	L[K:] = [1] * (N - K)
else:
	L[K:] = [10 ** 9] * (N - K)
print(*L)


(N, K, S) = map(int, input().split())
mod = 10 ** 9
rlt = [S] * K + [(S + 1) % mod] * (N - K)
print(' '.join(map(str, rlt)))


(n, k, s) = map(int, input().split())
if s == 10 ** 9:
	l = [1] * (n - k) + [s] * k
else:
	l = [s + 1] * (n - k) + [s] * k
print(' '.join(map(str, l)))


(n, k, s) = map(int, input().split())
mod = 10 ** 9
l = [s] * k + [(s + 1) % mod] * (n - k)
print(*l)


(n, k, s) = map(int, input().split())
if s >= 3:
	print(*[s] * k + [s - 1] * (n - k))
else:
	print(*[s] * k + [s + 1] * (n - k))


(N, K, S) = map(int, input().split())
A = []
for i in range(K):
	A.append(S)
for i in range(N - K):
	A.append(min(10 ** 9 - 1, S + 1))
print(*A)


(N, K, S) = map(int, input().split())
w = 10 ** 9
if S == w:
	w = 1
ans = [S] * K + [w] * (N - K)
print(*ans)


(n, k, s) = map(int, input().split())
print(*[s] * k + [2 ** 29] * (n - k))


(n, k, s) = map(int, input().split())
other = s + 1
if other > int(1000000000.0):
	other -= 2
print(*[s] * k + [other] * (n - k))


(N, K, S) = map(int, input().split())
a = (S + 1) % pow(10, 9)
answer = [S] * K + [a] * (N - K)
print(' '.join(map(str, answer)))


(N, K, S) = map(int, input().split())
n = [278] * N
for i in range(K):
	n[i] = S
for i in range(N):
	print(n[i], end=' ')


(n, k, s) = map(int, input().split())
ans = [s if i < k else (s + 1) % 10 ** 9 for i in range(n)]
print(' '.join(map(str, ans)))


(n, k, s) = map(int, input().split())
ans = [s] * k + [10 ** 9 - (s == 10 ** 9)] * (n - k)
print(*ans)


(n, k, s) = map(int, input().split())
ans = [s] * k
if s <= 100:
	zeros = [10 ** 9] * (n - k)
else:
	zeros = [s - 1] * (n - k)
ans.extend(zeros)
print(*ans)


(n, k, s) = map(int, input().split())
ans = (str(s) + ' ') * k + (str(s - 1 or 8) + ' ') * (n - k)
print(ans[:-1])


(N, K, S) = map(int, input().split())
l = [S] * K
if S == 10 ** 9:
	t = [S - 1] * (N - K)
else:
	t = [S + 1] * (N - K)
print(*l + t)


(n, k, s) = map(int, input().split())
tmp = s + 11 if s < 10 ** 9 else s - 11
li = [s] * k + [tmp] * (n - k)
print(*li)


INF = int(1000000000.0)
(n, k, s) = map(int, input().split())
if s == INF:
	INF -= 1
ans = [INF] * n
for i in range(k):
	ans[i] = s
print(*ans)


(N, K, S) = map(int, input().split())
a = [10 ** 9 if S == 1 else S - 1] * N
for i in range(K):
	a[i] = S
print(' '.join(map(str, a)))


(N, K, S) = map(int, input().split())
A = [S] * K + [S - 1 if S > 2 else 100] * (N - K)
print(*A)


(N, K, S) = map(int, input().split())
d = S + 1 if S < 10 ** 9 else 1
print(' '.join(map(str, (S,) * K + (d,) * (N - K))))


(N, K, S) = map(int, input().split())
ans = []
for i in range(K):
	ans.append(S)
for j in range(N - K):
	ans.append(114514)
print(*ans)


(N, K, S) = map(int, input().strip().split(' '))
_S = 1 if S == 1000000000 else S + 1
ans = [S] * K + [_S] * (N - K)
print(*ans)