Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

F. Покупка блюд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В городе живут $$$m$$$ людей. Также в городе есть в продаже $$$n$$$ блюд, где $$$i$$$-е блюде имеет цену $$$p_i$$$, уровень $$$s_i$$$ и симпатичность $$$b_i$$$. У $$$j$$$-го человека есть доход $$$inc_j$$$ и предпочтительная симпатичность $$$pref_j$$$.

Ни один человек никогда не купит блюдо, уровень которого ниже, чем его доход. Также, ни один человек не может позволить купить себе блюдо, с ценой выше, чем его доход. Иными словами, человек $$$j$$$ может купить блюдо $$$i$$$, если $$$p_i \leq inc_j \leq s_i$$$.

Также человек $$$j$$$ может купить блюдо $$$i$$$, только если $$$|b_i-pref_j| \leq (inc_j-p_i)$$$. Иначе говоря, если цена блюда на $$$k$$$ меньше, чем доход какого-то человека, то этот человек согласен на не более чем $$$k$$$ абсолютную разницу между симпатичностью блюда и предпочитаемой симпатичностью этого человека.

Выведите количество блюд, которые может купить каждый человек в городе.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$), количество блюд, продаваемых в городе и количество людей, в нём живущих.

Вторая строка содержит $$$n$$$ целых чисел $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$) — цена каждого блюда.

Третья строка содержит $$$n$$$ целых чисел $$$s_i$$$ ($$$1 \leq s_i \leq 10^9$$$) — уровень каждого блюда.

Четвёртая строка содержит $$$n$$$ целых чисел $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$) — симпатичность каждого блюда.

Пятая строка содержит $$$m$$$ целых чисел $$$inc_j$$$ ($$$1 \leq inc_j \leq 10^9$$$) — доход каждого человека.

Шестая строка содержит $$$m$$$ целых чисел $$$pref_j$$$ ($$$1 \leq pref_j \leq 10^9$$$) — предпочтительная симпатичность для каждого человека.

Гарантируется, что для всех целых чисел $$$i$$$ от $$$1$$$ до $$$n$$$, верно, что $$$p_i \leq s_i$$$.

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

Выведите $$$m$$$ целых чисел — количество блюд, которые может купить каждый человек, живущий в городе.

Примеры
Входные данные
3 3
2 1 3
2 4 4
2 1 1
2 2 3
1 2 4
Выходные данные
1 2 0
Входные данные
4 3
1 2 1 1
3 3 1 3
2 1 3 2
1 1 3
1 2 1
Выходные данные
0 2 3
Примечание

В первом примере первый человек может купить блюдо $$$2$$$, второй человек может купить блюда $$$1$$$ и $$$2$$$, а третий человек не может купить ни одного блюда.

Во втором примере первый человек не может купить ни одного блюда, второй человек может купить блюда $$$1$$$ и $$$4$$$, а третий человек может купить блюда $$$1$$$, $$$2$$$ и $$$4$$$.