题目描述

小 B 在统计一场晚会的报名节目。节目类型一共有 $m$ 种，用 $1$ 到 $m$ 的整数编号。他先数出每一类节目各有多少个。

如果某一类节目的数量大于其余所有类数量之和，节目单就失衡了。此时小 B 要把这一类的数量削减，直到它恰好等于其余所有类的数量之和。削减只会发生在这一个类型上。

请你输出每一类节目最终保留的数量。

输入格式

第一行两个整数 $n,m$，分别表示报名节目总数和节目类型总数。

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个节目的类型。

输出格式

一行 $m$ 个整数，第 $i$ 个数表示第 $i$ 类节目最终保留的数量，相邻两数之间用一个空格隔开。

样例

9 4
1 2 2 3 2 4 2 2 2

1 3 1 1

7 3
1 1 1 1 2 2 3

3 2 1

8 2
1 2 1 2 1 2 1 2

4 4

样例解释

样例 1：四类数量为 $1,6,1,1$。类型 $2$ 的数量 $6>1+1+1=3$，削减到 $3$，其他类型不变。

样例 2：三类数量为 $4,2,1$。类型 $1$ 的数量 $4>2+1=3$，削减到 $3$。总数是奇数时也可能失衡。

样例 3：两类数量都是 $4$，均未严格超过其余之和，不需要削减。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 100$，每个节目类型都在 $1$ 到 $m$ 之间。