C - Subarray Sum 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

3 つの整数 N, K, S が与えられます。

1 以上 10^9 以下の整数からなる長さ N の数列 A_1, A_2, ..., A_N であって、 以下の条件を満たすものをひとつ求めてください。 なお、制約の項で記述される条件のもとで、このような数列は必ず存在することが証明できます。

  • 1 \leq l \leq r \leq N を満たす整数の組 (l, r) であって、 A_l + A_{l + 1} + \cdots + A_r = S を満たすものはちょうど K 個ある。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq K \leq N
  • 1 \leq S \leq 10^9
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K S

出力

条件を満たす数列を以下の形式で出力せよ。

A_1 A_2 ... A_N

入力例 1

4 2 3

出力例 1

1 2 3 4

問題文の条件を満たす (l, r) は (1, 2) と (3, 3) の 2 個あります。

入力例 2

5 3 100

出力例 2

50 50 50 30 70

Score : 400 points

Problem Statement

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

Sample Input 1

4 2 3

Sample Output 1

1 2 3 4

Two pairs (l, r) = (1, 2) and (3, 3) satisfy the condition in the statement.

Sample Input 2

5 3 100

Sample Output 2

50 50 50 30 70