E. Минимальное влияние
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте, что вы — владелец новостного сайта и хотите изучить, как некоторые новости влияют на ваших пользователей.

У вас есть $$$n$$$ новостей, для каждой вы уже определили два параметра: насколько она касается политики $$$p_i$$$ и на сколько — культуры $$$c_i$$$.

Также у вас есть $$$m$$$ пользователей, влияние новостей на которых вы хотите изучить. Для каждого человека вы уже определили три параметра: толерантность к политическим новостям $$$tp_j$$$, толерантность к новостям культуры $$$tc_j$$$ и «зону влияния» $$$d_j$$$.

Силу влияния политики $$$I_p(i, j)$$$ и культуры $$$I_c(i, j)$$$ в новости $$$i$$$ на пользователя $$$j$$$ можно посчитать по следующим формулам:

$$$$$$ \begin{array}{ c c } I_p(i, j) = \begin{cases} 0 & \text{if } p_i \lt tp_j \\ p_i & \text{if } tp_j \le p_i \lt tp_j + d_j \\ tp_j + d_j & \text{if } p_i \ge tp_j + d_j \end{cases}, & I_c(i, j) = \begin{cases} 0 & \text{if } c_i \lt tc_j \\ c_i & \text{if } tc_j \le c_i \lt tc_j + d_j \\ tc_j + d_j & \text{if } c_i \ge tc_j + d_j \end{cases} \end{array}. $$$$$$

Другими словами, пока объем политики $$$p_i$$$ меньше уровня толерантности $$$tp_j$$$, то на пользователя она не влияет. В противном случае тема начинает раздражать пользователя, но не более чем до $$$tp_j + d_j$$$. Объем культуры в новости влияет таким же образом.

Суммарное влияние новости $$$i$$$ на пользователя $$$j$$$ равно $$$I(i, j) = I_p(i, j) + I_c(i, j)$$$.

Определите для каждого пользователя $$$j$$$ минимальное влияние $$$I(i, j)$$$ среди всех новостей $$$i$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество новостей.

Во второй строке заданы $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le 10^6$$$) — содержание политики в каждой новости.

В третьей строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 10^6$$$) — содержание культуры в каждой новости.

В четвертой строке задано одно целое число $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — количество пользователей.

В пятой строке заданы $$$m$$$ целых чисел $$$tp_1, tp_2, \dots, tp_m$$$ ($$$0 \le tp_j \le 10^6$$$) — толерантность к политике каждого пользователя.

В шестой строке заданы $$$m$$$ целых чисел $$$tc_1, tc_2, \dots, tc_m$$$ ($$$0 \le tc_j \le 10^6$$$) — толерантность к культуре каждого пользователя.

В седьмой строке заданы $$$m$$$ целых чисел $$$d_1, d_2, \dots, d_m$$$ ($$$0 \le d_j \le 10^6$$$) — зона влияния каждого пользователя.

Выходные данные

Для каждого пользователя выведите одно целое число — минимальное влияние $$$I(i, j)$$$ среди всех новостей.

Примеры
Входные данные
6
2 4 1 6 0 10
3 2 6 1 9 0
5
0 0 0 1 5
0 0 9 5 2
9 4 8 2 2
Выходные данные
5
4
1
2
2
Входные данные
5
75 19 53 12 10
34 75 67 84 95
5
55 14 46 97 14
78 61 56 23 33
10 4 7 11 3
Выходные данные
0
18
53
34
36