問題文

kazuppa王国の国王であるkazuppa君は毎週日曜日に「明日は月曜日！」と言うことで国民を怒らせるのが趣味です。

以降、月日が書かれているものは全て年は2026年であるとします。

kazuppa王国の暦は正整数 $K,N$ と正整数列 $(D_1,D_2,\dotsc,D_K)$ によって以下のように表されます。

• $1$ 年は $1,2,\dotsc,K$ 月の計 $K$ カ月からなり、$i$ 月は $1,2,\dotsc,D_i$ 日の計 $D_i$ 日からなる。
• $1$ 月 $1$ 日は日曜日であり、その翌日から $N-1$ 日後までは全て日曜日ではない。
• 一週間は $N$ 日である。つまり、ある日が日曜日であるとき、その $N$ 日後 と $N$ 日前も日曜日である。

kazuppa君は以下の操作を好きな回数行うことができます。

• 整数の組 $(i,j)\ (1\leq i,j\leq K)$ を一つ選ぶ。 $D_i$ を $1$ 減らし、$D_j$ を $1$ 増やす。ただし操作の過程で $D_i= 0$ を満たす $i$ が存在してはならない。

$m=1,2,\dotsc,K$ について以下の独立な問題に答えてください。

変更後の暦における $m$ 月の日曜日の数が変更前の暦における $m$ 月の日曜日の日数より真に大きくなるために必要な操作回数の最小値を求めてください。ただし、条件を満たすような操作が存在しない場合は -1 を出力してください。

制約

• $1\leq K\leq 2\times 10^5$
• $2\leq N\leq 2\times 10^{14}$
• $1\leq D_i\leq 10^9$
• 入力はすべて整数

入力

$K\ N$
$D_1\ D_2\ \dotsc\ D_K$

出力

$K$ 行出力して下さい。

$i$ 行目には $m=i$ の時の答えを出力してください。

サンプル

6 3
1 6 9 2 3 1

3
3
1
1
3
3

1 2
169231

-1

2 2
2 2

1
-1