AT_abc373_e [ABC373E] How to Win the Election

[problemUrl]: https://atcoder.jp/contests/abc373/tasks/abc373_e $ 1,2,\ldots,N $ の番号のついた $ N $ 人の候補者で選挙が行われています。$ K $ 票の投票があり、現在一部の開票作業が行なわれました。 これまでの開票作業では、$ i $ 番目の候補者に $ A_i $ 票が入りました。 全ての票が開票された後、$ i $ 番目 $ (1\ \leq\ i\ \leq\ N) $ の候補者はその候補者より多く票を獲得した候補者が $ M $ 人未満であるとき、かつその時に限り当選します。複数の候補者が当選することもあります。 各候補者が当選を確定させるためには残りの票のうち最小で何票追加で票が必要か求めてください。 より厳密には、$ i\ =\ 1,2,\ldots,N $ に対して次の問題を解いてください。 次の条件を満たす $ K\ -\ \displaystyle{\sum_{i=1}^{N}}\ A_i $ 以下の非負整数 $ X $ が存在するか判定し、存在するならその最小値を求めてください。 - これ以降の開票作業で $ i $ 番目の候補者へ $ X $ 票入るなら、$ i $ 番目の候補者は必ず当選する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

候補者 $ i $ が当選を確定させるために必要な票数を $ C_i $ としたとき、$ C_1,C_2,\ldots,C_N $ を空白区切りで出力せよ。 ただし、候補者 $ i $ がすでに当選を確定させている場合は $ C_i=0 $、候補者 $ i $ が当選を確定させることができない場合は $ C_i=-1 $ とします。

### 制約 - $ 1\ \leq\ M\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ K\ \leq\ 10^{12} $ - $ 0\ \leq\ A_i\ \leq\ 10^{12} $ - $ \displaystyle{\sum_{i=1}^{N}\ A_i}\ \leq\ K $ - 入力はすべて整数 ### Sample Explanation 1 すでに $ 14 $ 票の開票が終了しており、残りの票数は $ 2 $ 票です。 答えるべき $ C $ は $ (2,\ -1,\ 1,\ -1,\ 0) $ です。たとえば： - 候補者 $ 1 $ は追加で $ 2 $ 票得ることで当選を確定することができます。追加で $ 1 $ 票獲得することでは当選を確定することができないので、$ C_1\ =\ 2 $ です。 - 候補者 $ 2 $ はどのようにしても（例えば、残り $ 2 $ 票をすべて獲得しても）当選することが不可能なので、 $ C_2\ =\ -1 $ です。