问题描述

你是否了解传统的日本抽签游戏"阿弥陀籤"?

在进行阿弥陀籤时，首先画出 $N$ 条平行的竖线。然后，在其中画出 $M$ 条横线。每条横线必须连接相邻的两条竖线，并且不能有两条或两条以上的横线位于相同高度上。假设第 $i$ ($1\leq i\leq M$) 条横线连接第 $A_i$ ($1\leq A_i < N$) 条竖线和第 $A_i + 1$ 条竖线。

当 $N=5$，$M=7$，$A=\{1,4,3,4,2,3,1\}$ 时，阿弥陀籤的情况如下所示。在抽签时，选定一条竖线，并从其上端向下进行抽签。如果遇到横线，必须转弯，并且不能朝上追溯竖线。例如，在这个例子中，从左起数第四条竖线开始抽签，会到达左起数第三条竖线。

然而，如今，人们不断强调大数据。为了使阿弥陀籤继续存在下去，它必须变得更大，并与大数据竞争。

因此，让我们考虑通过将阿弥陀籤垂直连接 $D$ 次来创建一个巨大的阿弥陀籤。例如，将前面提到的阿弥陀籤连接两次，就得到以下结果。在这种情况下，从左起数第四条竖线开始抽签，会到达左起数第五条竖线。

虽然我们已经制作出了巨大的阿弥陀籤，但如果不能有效地计算使用该巨大阿弥陀籤进行抽签的结果，那么制作巨大阿弥陀籤就没有意义。换句话说，我们需要编写一个程序，对于满足 $1\leq k\leq N$ 的所有整数 $k$，计算当从巨大阿弥陀籤的左起第 $k$ 条竖线开始抽签时，最终会到达下端的左起多少条竖线。

---

输入

输入从标准输入流中以以下格式给出：

$N$ $M$ $D$ $A_1$ $A_2$ $...$ $A_M$

• 第一行包含三个整数，分别表示原始阿弥陀籤的竖线数量 $N$ ($2\leq N\leq 10^5$)，横线数量 $M$ ($0\leq M\leq 2\times 10^5$)，连接原始阿弥陀籤的次数 $D$ ($1\leq D\leq 10^9$)。
• 第二行包含 $M$ 个整数 $A_i$ ($1\leq i\leq M$)，表示原始阿弥陀籤中的横线信息。

部分测试点

该问题的测试案例分为四个组，每个组的得分不同。

• 对于第一组，测试案例满足 $D = 1$。正确解答该组中的所有测试案例可获得 10 分。
• 对于第二组，测试案例满足 $N\leq 1,000$ 和 $D\leq 1,000$。正确解答该组中的所有测试案例可获得 20 分。
• 对于第三组，测试案例满足 $N\leq 8$。正确解答该组中的所有测试案例可获得 20 分。
• 对于第四组，测试案例没有其他限制。正确解答该组中的所有测试案例可获得 50 分。

输出

输出共 $N$ 行。其中第 $k$ 行表示从巨大阿弥陀籤的左起第 $k$ 条竖线开始抽签时，最终到达下端的左起多少条竖线。请输出整数。

输出结束时要换行。

---

输入示例1

5 7 1
1 4 3 4 2 3 1

输出示例1

4
2
5
3
1

此示例对应于问题文中的第一个示意图。

---

输入示例2

5 7 2
1 4 3 4 2 3 1

输出示例2

3
2
1
5
4

此示例对应于问题文中的第二个示意图。请注意，此测试案例未满足第一组的限制。

---

输入示例3

10 20 300
9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6

输出示例3

3
7
2
4
5
9
6
1
8
10

请注意，此测试案例未满足第一组和第三组的限制。

---