J - Incremental Machine

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ があり、はじめ、すべての要素は $0$ で初期化されています。

数直線上を移動する機械があり、整数 $x$ を内部状態として持ちます。
はじめ、機械は座標 $1$ にあり、$x=1$ です。

整数列 $A$ に対して以下のクエリを $Q$ 回処理します。

$i$ 番目のクエリでは、$1$ 以上 $N$ 以下の整数 $T_i$ が与えられます。
機械の座標が $T_i$ になるまで以下を順に繰り返します。

1. 機械の現在の座標を $p$ として、$A_p$ に $x$ を加算する。
2. $x$ に $1$ を加算する。
3. 機械が $T_i$ に近づく方向に $1$ 進む。
   厳密に言えば、$p<T_i$ ならば機械は座標 $p+1$ に移動し、$p>T_i$ ならば機械は座標 $p-1$ に移動する。

クエリの開始時点で機械の座標が既に $T_i$ である場合、そのクエリでは何も行いません。また、機械の座標と $x$ の値はクエリごとに初期化されず、次のクエリに引き継がれます。

すべてのクエリを処理した後の数列 $A$ を求めてください。

制約

• $1\le N,Q\le2\times10^5$
• $1\le T_i\le N$
• 入力は全て整数

入力

出力

全てのクエリを処理した後の整数列 $A=(A_1,A_2,\cdots,A_N)$ を以下の形式で出力してください。

入力例1

5 3
3
2
5

出力例1

1 6 8 6 0

機械はクエリ $i$ で次のように動きます。

• $i=1\ (T_1=3)$ ： $1\to2\to3$
• $i=2\ (T_2=2)$ ： $3\to2$
• $i=3\ (T_3=5)$ ： $2\to3\to4\to5$

この移動によって $x$ は次のように変化します。

• $i=1\ (T_1=3)$ ： $1\to2\to3$
• $i=2\ (T_2=2)$ ： $3\to4$
• $i=3\ (T_3=5)$ ： $4\to5\to6\to7$

同様に、$A$ は次のように変化します。

• $i=1\ (T_1=3)$ ： $(0,0,0,0,0)\to(1,0,0,0,0)\to(1,2,0,0,0)$
• $i=2\ (T_2=2)$ ： $(1,2,0,0,0)\to(1,2,3,0,0)$
• $i=3\ (T_3=5)$ ： $(1,2,3,0,0)\to(1,6,3,0,0)\to(1,6,8,0,0)\to(1,6,8,6,0)$

よって、最終的な結果である $(1,6,8,6,0)$ を出力してください。

入力例2

3 3
1
2
3

出力例2

1 2 0

機械が移動しないことや、前のクエリと同じ向きに移動することもあることに注意してください。

入力例3

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

出力例3

32 64 123 138 138 138 138 100 53 22