長いだけのネクタイ (Just Long Neckties)

あなたは Just Odd Inventions 社を知っているだろうか？この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社は新商品「長いだけのネクタイ」を開発した．ネクタイは \(N + 1\) 種類あり，各種類には \(1\) から \(N + 1\) までの番号がついている．\(i\) 番目 (\(1 \leqq i \leqq N + 1\)) の種類のネクタイの長さは \(A_i\) である．

JOI 社は社員を集め，ネクタイの試着会を行うことにした．試着会には \(N\) 人の社員が参加し，\(j\) 人目 (\(1 \leqq j \leqq N\)) の社員がはじめに付けているネクタイの長さは \(B_j\) である．

試着会は以下の手順で行われる予定である．

1. まず，試着会で使わないネクタイを \(1\) 種類選ぶ．
2. 次に，各社員はそれ以外のネクタイから試着するネクタイを \(1\) 種類選ぶ．ただし，どの \(2\) 人も同じ種類のネクタイを選ばないようにする．
3. 最後に，各社員は今付けているネクタイを外し，先ほど選んだネクタイを試着する．

長さ \(b\) のネクタイを付けていた社員が，長さ \(a\) のネクタイを試着すると大きさ \(\max\{a − b, 0\}\) の奇妙さを感じる．(ここで，\(\max\{a − b, 0\}\) は，\(a - b\) と \(0\) のうち小さくない方を表す．) 試着会において各社員の感じる奇妙さの最大値を，その試着会の奇妙さとする．

試着会で使わないネクタイが \(k\) 番目の種類のネクタイのとき，試着会の奇妙さとして考えられる最小の値を \(C_k\) とする．

各種類のネクタイの長さ，各社員がはじめに付けているネクタイの長さが与えられた時，\(C_1, C_2, \ldots, C_{N + 1}\) の値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

\(N\)
\(A_1\) \(\cdots\) \(A_{N + 1}\)
\(B_1\) \(\cdots\) \(B_N\)

\(C_1, C_2, \ldots, C_{N + 1}\) の値を，空白区切りで標準出力に \(1\) 行で出力せよ．

• \(1 \leqq N \leqq 200\,000\).
• \(1 \leqq A_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N + 1\))．
• \(1 \leqq B_j \leqq 1\,000\,000\,000\) (\(1 \leqq j \leqq N\))．

1. (\(1\) 点) \(N \leqq 10\).
2. (\(8\) 点) \(N \leqq 2\,000\).
3. (\(91\) 点) 追加の制約はない.

JOI 2020 · JCIOI · CC BY-SA 4.0