AT_joig2023_c 鐘 (Bell)

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_1, B_2, …, B_M $ で聞こえる鐘の音の強さを求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_M $

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

### 小課題 1. ( $ 20 $ 点) $ N = 1 $ ， $ M \leqq 1\,000 $ ． 2. ( $ 20 $ 点) $ N \leqq 1\,000 $ ， $ M \leqq 1\,000 $ ． 3. ( $ 60 $ 点) 追加の制約はない． ### Sample Explanation 1 この入力例では，座標 $ 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 $ を出力する． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 2 - 鐘 $ 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 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 2, 3 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 250\,000 $ ． - $ 1 \leqq M \leqq 250\,000 $ ． - $ 1 \leqq K \leqq 10^9 $ ． - $ 0 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ A_i \lt A_{i+1} $ ( $ 1 \leqq i \leqq N - 1 $ )． - $ 0 \leqq B_j \leqq 10^9 $ ( $ 1 \leqq j \leqq M $ )． - $ B_j ≠ B_k $ ( $ 1 \leqq j < k \leqq M $ )． - 入力される値はすべて整数である．