縄(Rope)

赤ちゃんのJOI くんは縄で遊んでいる．縄の長さは $N$ であり，左右にまっすぐ伸びている．縄は太さ1，長さ1 の紐(ひも) が $N$ 個つながってできている．縄には $M$ 種類の色が使われており，左から $i$ 番目の紐の色は $C_i$ ($1 \leq C_i \leq M$) である．

JOI くんは縄をより合わせて短くしていく．具体的には，以下の操作を縄の長さが2 となるまで繰り返す．

縄の長さを $L$ とする．ある整数 $j$ ($1 \leq j < L$) を取り，左から長さ $j$ の位置が新たに左の端点となるよう，縄をより合わせていく．すなわち，
- $j \leq L/2$ のとき，各 $i$ ($1 \leq i \leq j)$ について，左から $i$ 番目の紐と，左から $2j - i + 1$ 番目の紐をより合わせる．このとき元々右の端点だった位置は引き続き右の端点となり，縄の長さは $L - j$ となる．
- $j > L/2$ のとき，各$i$ ($2j - L + 1 \leq i \leq j$) について，左から $i$ 番目の紐と，左から $2j - i + 1$ 番目の紐をより合わせる．このとき元々左の端点だった位置は右の端点となり，縄の長さは $j$ となる．
このとき，より合わされる各紐の組について，色を揃えなければならない．紐はより合わせる直前に，任意の色に塗り替えることができるが，塗り替えた場合その太さと同じだけのコストがかかる．色を揃えたのち，紐はより合わされ，できた紐の太さはより合わされた2 つの紐の太さの和となる．

JOI くんは，縄の長さが2 となるまでに行う操作のコストの総和を最小化したいと思っている．JOI くんはすべての色について，最終的な縄がその色を含むように操作を行った場合のコストの総和の最小値を求めたいと思っている．

あなたの仕事はJOI くんに代わってこの問題を解くことである．

課題

はじめの縄を構成する紐の色が与えられたとき，それぞれの色について，縄がその色を含み，かつ長さを2 とするのに必要なコストの最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には2 個の整数 $N, M$ が空白を区切りとして書かれている．これらは縄を構成する紐が $N$ 個あり，それらの色が $M$ 種類あることを表す．
2 行目には $N$ 個の整数 $C_1, C_2, ... ,C_N$ が空白を区切りとして書かれている．これらは左から $i$ 番目の紐の色が $C_i$ であることを表す．

出力

標準出力に $M$ 行で出力せよ．$M$ 行のうちの $c$ ($1 \leq c \leq M$) 行目には，最終的な縄の長さが2 となり，その縄に色 $c$ を含むようにより合わせるためのコストの総和の最小値を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

$ 2 \leq N \leq 1 000 000． $
$ 1 \leq M \leq N．$
$ 1 \leq C_i \leq M (1 \leq i \leq N)．$
$ 1 \leq c \leq M を満たすすべての整数 c について，C_i = c となる i が存在する.$

入出力例

入力例1

5 3
1 2 3 3 2

出力例1

2
1
1

以下のような操作で，色1 を含むようコスト2 で長さ2 により合わせることができる．

左から2 番目の紐を色1 に塗り替え，左から長さ1 の位置が端点となるようより合わせる．左から順に縄の色は1, 3, 3, 2 となり，太さは2, 1, 1, 1 となる．
左から4 番目の紐の色を1 に塗り替え，左から長さ2 の位置が端点となるようより合わせる．左から順に縄の色は3, 1 となり，太さは2, 3 となる．

また，以下のような操作で，色2, 3 を含むようコスト1 で長さ2 により合わせることができる．