Dish Shopping

题意翻译

- $n$ 种菜和 $m$ 个人 - 每种菜 $i$ 有三个属性 $p_{i}, s_{i}, b_{i}$ - 每个人 $j$ 有两个属性 $i n c_{j}, p r e f_{j}$。一个人 $j$ 能品尝菜 $i$ 当且仅当 $p_{i} \leq$ inc $_{j} \leq s_{i}$ 且 $\left|b_{i}-p r e f_{j}\right| \leq i n c_{j}-p_{i}$ - 求每个人能品尝多少种菜 - $1 \leq n, m \leq 10^{5}$, 其他数据均为 $10^{9}$ 级别

题目描述

There are $ m $ people living in a city. There are $ n $ dishes sold in the city. Each dish $ i $ has a price $ p_i $ , a standard $ s_i $ and a beauty $ b_i $ . Each person $ j $ has an income of $ inc_j $ and a preferred beauty $ pref_j $ . A person would never buy a dish whose standard is less than the person's income. Also, a person can't afford a dish with a price greater than the income of the person. In other words, a person $ j $ can buy a dish $ i $ only if $ p_i \leq inc_j \leq s_i $ . Also, a person $ j $ can buy a dish $ i $ , only if $ |b_i-pref_j| \leq (inc_j-p_i) $ . In other words, if the price of the dish is less than the person's income by $ k $ , the person will only allow the absolute difference of at most $ k $ between the beauty of the dish and his/her preferred beauty. Print the number of dishes that can be bought by each person in the city.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n \leq 10^5 $ , $ 1 \leq m \leq 10^5 $ ), the number of dishes available in the city and the number of people living in the city. The second line contains $ n $ integers $ p_i $ ( $ 1 \leq p_i \leq 10^9 $ ), the price of each dish. The third line contains $ n $ integers $ s_i $ ( $ 1 \leq s_i \leq 10^9 $ ), the standard of each dish. The fourth line contains $ n $ integers $ b_i $ ( $ 1 \leq b_i \leq 10^9 $ ), the beauty of each dish. The fifth line contains $ m $ integers $ inc_j $ ( $ 1 \leq inc_j \leq 10^9 $ ), the income of every person. The sixth line contains $ m $ integers $ pref_j $ ( $ 1 \leq pref_j \leq 10^9 $ ), the preferred beauty of every person. It is guaranteed that for all integers $ i $ from $ 1 $ to $ n $ , the following condition holds: $ p_i \leq s_i $ .

输出格式

Print $ m $ integers, the number of dishes that can be bought by every person living in the city.

输入输出样例

输入样例 #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 

说明

In the first example, the first person can buy dish $ 2 $ , the second person can buy dishes $ 1 $ and $ 2 $ and the third person can buy no dishes. In the second example, the first person can buy no dishes, the second person can buy dishes $ 1 $ and $ 4 $ , and the third person can buy dishes $ 1 $ , $ 2 $ and $ 4 $ .