← 返回题目列表

AtCoder · awc0024_d

D. 用荧光笔突出显示

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥在备考时用荧光笔突出显示教科书的重要部分。

考虑教科书中的特定行。该行包含 N 字符排列在水平行中,从左到右作为位置编号 1, 2, \ldots, N.

荧光标记高桥使用标记 W 每次使用时连续的字符。高桥总共使用了该荧光标记 K 次。在 i第标记 (1 \leq i \leq K),他选择了起始位置 L_i 并标记 W 位置的连续字符 L_i 到位置 L_i + W - 1。标记范围绝不会超出该线(即 1 \leq L_i \leq N - W + 1 成立)。

在不同的标记中可以选择相同的起始位置。此外,即使起始位置不同,它们的标记范围也可能重叠。每个位置的字符被标记的次数是包括该位置的标记操作的总数。

所有标记操作完成后,确定每个位置的字符总共被标记了多少次。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq N
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq L_i \leq N - W + 1 (1 \leq i \leq K)
  • 所有输入均为整数

输入

N W K
L_1
L_2
\vdots
L_K
  • 第一行包含字符总数 N,荧光标记一次标记的字符数 W,以及标记数量 K,用空格分隔。
  • 的 树的 i-th (1 \leq i \leq K) 以下内容 K 行包含起始位置 L_i 的 i-第标记。

输出

输出 N 单行上用空格分隔的整数。的 j-th (1 \leq j \leq N) 整数表示该位置的字符出现的次数 j 已标记。


示例输入 1

10 3 2
2
5

示例输出 1

0 1 1 1 1 1 1 0 0 0

示例输入 2

8 4 3
1
3
2

示例输出 2

1 2 3 3 2 1 0 0

示例输入 3

15 5 6
1
3
7
11
2
7

示例输出 3

1 2 3 3 3 2 3 2 2 2 3 1 1 1 1