Problem: 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 ≤ inc_j ≤ s_i.

Also, a person j can buy a dish i, only if |b_i-pref_j| ≤ (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.

Input

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 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 ≤ p_i ≤ 10^9), the price of each dish.

The third line contains n integers s_i (1 ≤ s_i ≤ 10^9), the standard of each dish.

The fourth line contains n integers b_i (1 ≤ b_i ≤ 10^9), the beauty of each dish.

The fifth line contains m integers inc_j (1 ≤ inc_j ≤ 10^9), the income of every person.

The sixth line contains m integers pref_j (1 ≤ pref_j ≤ 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 ≤ s_i.

Output

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

Examples

Input


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


Output


1 2 0 

Input


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


Output


0 2 3 

Note

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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int N, M;
signed long long P[101010], S[101010], B[101010], inc[101010], pref[101010];
template <class V, int ME>
class BIT {
 public:
  V bit[1 << ME];
  V operator()(int e) {
    if (e < 0) return 0;
    V s = 0;
    e++;
    while (e) s += bit[e - 1], e -= e & -e;
    return s;
  }
  void add(int e, V v) {
    e++;
    while (e <= 1 << ME) bit[e - 1] += v, e += e & -e;
  }
};
BIT<int, 20> btp, btm;
vector<pair<int, int>> ev;
int ret[101010];
int num;
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> M;
  vector<signed long long> CP, CM;
  CP.push_back(-1LL << 40);
  CM.push_back(-1LL << 40);
  for (i = 0; i < (N); i++) {
    cin >> P[i];
    ev.push_back({P[i], i});
  }
  for (i = 0; i < (N); i++) {
    cin >> S[i];
    ev.push_back({S[i], 200000 + i});
  }
  for (i = 0; i < (N); i++) {
    cin >> B[i];
    CP.push_back(B[i] + P[i]);
    CM.push_back(P[i] - B[i]);
  }
  for (i = 0; i < (M); i++) {
    cin >> inc[i];
    ev.push_back({inc[i], 100000 + i});
  }
  for (i = 0; i < (M); i++) {
    cin >> pref[i];
    CP.push_back(inc[i] + pref[i]);
    CM.push_back(inc[i] - pref[i]);
  }
  sort((CP.begin()), (CP.end()));
  sort((CM.begin()), (CM.end()));
  CP.erase(unique((CP.begin()), (CP.end())), CP.end());
  CM.erase(unique((CM.begin()), (CM.end())), CM.end());
  sort((ev.begin()), (ev.end()));
  for (auto& e : ev) {
    x = e.second;
    if (x < 100000) {
      num++;
      y = lower_bound((CP.begin()), (CP.end()), B[x] + P[x]) - CP.begin();
      btp.add(y, 1);
      y = lower_bound((CM.begin()), (CM.end()), P[x] - B[x]) - CM.begin();
      btm.add(y, 1);
    } else if (x < 200000) {
      x -= 100000;
      y = lower_bound((CP.begin()), (CP.end()), inc[x] + pref[x]) - CP.begin();
      ret[x] += btp(y);
      y = lower_bound((CM.begin()), (CM.end()), inc[x] - pref[x]) - CM.begin();
      ret[x] += btm(y);
      ret[x] -= num;
    } else {
      x -= 200000;
      num--;
      y = lower_bound((CP.begin()), (CP.end()), B[x] + P[x]) - CP.begin();
      btp.add(y, -1);
      y = lower_bound((CM.begin()), (CM.end()), P[x] - B[x]) - CM.begin();
      btm.add(y, -1);
    }
  }
  for (i = 0; i < (M); i++) cout << ret[i] << " ";
  cout << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}