← 返回题目列表

Codeforces · 1139/F

F. 菜品购物

中文机器翻译题面 查看原题

一座城市里居住着 $$$m$$$ 人。城里有卖$$$n$$$的菜肴。每道菜$$$i$$$都有价格$$$p_i$$$、标准$$$s_i$$$和美女$$$b_i$$$。每个人 $$$j$$$ 的收入为 $$$inc_j$$$ 和首选美女 $$$pref_j$$$。

一个人永远不会购买标准低于他收入的菜肴。而且,一个人买不起价格高于其收入的菜肴。换句话说,只有当$$$p_i \leq inc_j \leq s_i$$$ 时,一个人$$$j$$$ 才能购买$$$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$$$),每个人的首选美丽。

保证对于从 $$$1$$$ 到 $$$n$$$ 的所有整数 $$$i$$$,以下条件成立:$$$p_i \leq s_i$$$。

输出

打印 $$$m$$$ 整数,即居住在城市中的每个人可以购买的菜肴数量。

示例

输入 #1

3 3
2 1 3
2 4 4
2 1 1
2 2 3
1 2 4

输出 #1

1 2 0

输入 #2

4 3
1 2 1 1
3 3 1 3
2 1 3 2
1 1 3
1 2 1

输出 #2

0 2 3

注意

在第一个例子中,第一人可以购买菜肴$$$2$$$,第二人可以购买菜肴$$$1$$$和$$$2$$$,第三人不能购买菜肴。

在第二个示例中,第一人不能购买菜肴,第二人可以购买菜肴$$$1$$$和$$$4$$$,第三人可以购买菜肴$$$1$$$、$$$2$$$和$$$4$$$。