日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

問題文

JOI 市には 1 本の十分に長い道路がある．この道路は数直線とみなすことができ，各地点は 1 個の実数による座標で表される．

また，JOI 市にはこの道路に沿って N 個の鐘があり，座標の小さい順に 1 から N までの番号が付けられている．鐘 i (1 ≦ i ≦ N) は座標 A_i にある．

JOI 市では，1 年の終わりにこれらの鐘を一斉に鳴らすのが一大イベントとなっている．

どの鐘も，鳴らすとその鐘と同じ地点では強さ K の音で聞こえるが，距離が 1 離れるごとに聞こえる音の強さは 1 小さくなり，距離が K 以上離れると 0 になる．すなわち，鐘 i を鳴らしたとき，座標 x で聞こえる鐘 i の音の強さは max{ K - |x - A_i|, 0 } である．ただし，|t| は t の絶対値を表す．

すべての鐘を鳴らしたとき，座標 x で聞こえる鐘の音の強さは，座標 x で聞こえるそれぞれの鐘の音の強さの最大値である．

JOI 市にはこの道路に沿って M 個の家があり，古い方から順に 1 から M までの番号が付けられている．家 j (1 ≦ j ≦ M) は座標 B_j にある．

JOI 市の市長であるあなたは，すべての鐘を鳴らしたとき，それぞれの家で聞こえる鐘の音の強さを知りたい．

JOI 市の鐘と家の情報が与えられたとき，すべての鐘を鳴らしたときに座標 B₁, B₂, …, B_M で聞こえる鐘の音の強さを求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 250 000．
• 1 ≦ M ≦ 250 000．
• 1 ≦ K ≦ 10⁹．
• 0 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• A_i ＜ A_i+1 (1 ≦ i ≦ N - 1)．
• 0 ≦ B_j ≦ 10⁹ (1 ≦ j ≦ M)．
• B_j ≠ B_k (1 ≦ j ＜ k ≦ M)．
• 入力される値はすべて整数である．

小課題

1. (20 点) N = 1，M ≦ 1 000．
2. (20 点) N ≦ 1 000，M ≦ 1 000．
3. (60 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N M K
A₁ A₂ … A_N
B₁ B₂ … B_M

出力

M 行出力せよ．j 行目 (1 ≦ j ≦ M) には，すべての鐘を鳴らしたときに座標 B_j で聞こえる鐘の音の強さを出力せよ．

入出力例

入力例 1
1 5 10
20
20 15 28 10 32

出力例 1
10
5
2
0
0

この入力例では，座標 20 に鐘 1 がある．

• 鐘 1 を鳴らしたとき，座標 20 で聞こえる鐘 1 の音の強さは max{ 10 - |20 - 20|, 0 } = 10 である．したがって，1 行目には 10 を出力する．
• 鐘 1 を鳴らしたとき，座標 15 で聞こえる鐘 1 の音の強さは max{10 - |15 - 20|, 0 } = 5 である．したがって，2 行目には 5 を出力する．
• 鐘 1 を鳴らしたとき，座標 28 で聞こえる鐘 1 の音の強さは max{10 - |28 - 20|, 0 } = 2 である．したがって，3 行目には 2 を出力する．
• 鐘 1 を鳴らしたとき，座標 10 で聞こえる鐘 1 の音の強さは max{10 - |10 - 20|, 0 } = 0 である．したがって，4 行目には 0 を出力する．
• 鐘 1 を鳴らしたとき，座標 32 で聞こえる鐘 1 の音の強さは max{10 - |32 - 20|, 0 } = 0 である．したがって，5 行目には 0 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2
3 4 100
116 194 258
57 155 222 360

出力例 2
41
61
72
0

• 鐘 1,2,3 を鳴らしたとき，座標 57 で聞こえる音の強さはそれぞれ 41,0,0 である．したがって，すべての鐘を鳴らしたときに座標 57 で聞こえる音の強さはこれらの最大値である 41 である．そのため，1 行目には 41 を出力する．
• 鐘 1,2,3 を鳴らしたとき，座標 155 で聞こえる音の強さはそれぞれ 61,61,0 である．したがって，すべての鐘を鳴らしたときに座標 155 で聞こえる音の強さはこれらの最大値である 61 である．そのため，2 行目には 61 を出力する．
• 鐘 1,2,3 を鳴らしたとき，座標 222 で聞こえる音の強さはそれぞれ 0,72,64 である．したがって，すべての鐘を鳴らしたときに座標 222 で聞こえる音の強さはこれらの最大値である 72 である．そのため，3 行目には 72 を出力する．
• 鐘 1,2,3 を鳴らしたとき，座標 360 で聞こえる音の強さはそれぞれ 0,0,0 である．したがって，すべての鐘を鳴らしたときに座標 360 で聞こえる音の強さはこれらの最大値である 0 である．そのため，4 行目には 0 を出力する．

この入力例は小課題 2, 3 の制約を満たす．

入力例 3
10 10 10000
589 2398 6567 28817 29177 31636 45468 66751 82282 97509
2196 54498 80474 61644 18007 38759 85590 72172 79533 69959

出力例 3
9798
970
8192
4893
0
3291
6692
4579
7251
6792

この入力例は小課題 2, 3 の制約を満たす．