시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB51312661.905%

문제

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

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

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

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

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

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

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

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

입력

入力は以下の形式で与えられる.

N M K
A1 A2  AN
B1 B2  BM

출력

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

제한

  • 1 ≦ N ≦ 250 000
  • 1 ≦ M ≦ 250 000
  • 1 ≦ K ≦ 109
  • 0 ≦ Ai ≦ 109 (1 ≦ i ≦ N).
  • Ai < Ai+1 (1 ≦ i ≦ N - 1).
  • 0 ≦ Bj ≦ 109 (1 ≦ j ≦ M).
  • Bj ≠ Bk (1 ≦ j < k ≦ M).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
120

N = 1M ≦ 1 000

220

N ≦ 1 000M ≦ 1 000

360

追加の制約はない.

예제 입력 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 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.