小美和小团在玩一个游戏，游戏中有一个长度为 $n$ 的数组$a_1,a_2,...,a_n$ 和一个固定的整数$k$。游戏规则如下，双方都会执行最优策略:

第一步,小美选择一个非空的区间 $[l, r]$，将这个区间中的所有数字都乘上 $k$。

第二步, 小团选择一个非空的区间 $[l, r]$, 将这个区间中的所有数字都乘上 $k$。

记$sum=\sum\limits_{i=1}^n a_i$ 小团想让$sum$尽可能小，你需要求出最后 $sum$ 的值。

输入描述

第一行输入两个整数 n 和 k$(1 ≤ k ≤ 10^5, 1 ≤ n ≤ 1000; -10^5 ≤ a_i ≤ 10^5)$,代表数组长度和固定的整数。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$, $(-10^5≤ a_i ≤10^5)$代表数组。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

6 2
-1 -2 -3 1 2 3

输出

0

说明

小美会选择区间$[4, 6]$,数组变成{$-1,-2,-3,2,4,6$}；

小美会选择区间$[1,3]$,数组变成{$-2,-4,-6,2,4,6$}；

数组总和为 $0$。

题目内容

沉畀最近对图的度非常感兴趣。

如果一个子图是连通的，并且子图中的每个点的度都是大于等于k的，且这个子图不能更大（即与这个子图连接的所有点的度都小于k），那么这个子图就叫做k型子图。每个点可能存在于许多k型子图中，我们定义每个点的完美值为其所在的k型子图中最大的k。

现在，沉畀想要知道所有点的完美值。

图中黑色得到点表示完美值为1的点，黄色得到点表示完美值为2的点，蓝色的点表示完美值为3的点。

输入描述

第一行输入两个整数$n,m(1 \leq n,m \leq 1e6)$. 接下来$m$行，每行两个整数$u,v(1 \leq u,v \leq 1e6 u != v)$代表有一条连接$u$点和$v$点的边。

输出描述

输出为一行n个整数，代表$1-n$号点的完美值

样例1

输入

3 3
1 2
2 3
3 1

输出

2 2 2