Masala #1146

Xotira 16 MB Vaqt 1000 ms

Radio

Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun \(N\) ta Radio o’rnatilgan. Har bir radioning ovoz balandligi \(K\) ga teng. Radioda yangilik eshittirilganda \(A\)- koordinatada bo’lgan uyga \(B\)-koordinatada joylashtirilgan radioning ovozi \(max(K-|A-B|, 0)\) balandlikda eshitiladi. Sizga \(M\) ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida uchta butun son, \(N(1 \le N \le 250000)\), \(M(1 \le M \le 250000)\) va \(K(1 \le K \le 10^9)\) sonlari kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(B_i(1 \le i \le N, 0 \le B_i \le 10^9)\) Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, \(A_i(1 \le i \le M, 0 \le A_i \le 10^9)\) uylarning joylashgan koordinatalari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.

Misollar

#	input.txt	output.txt
1	1 5 10 20 20 15 28 10 32	10 5 2 0 0
2	3 4 100 116 194 258 57 155 222 360	41 61 72 0