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;
using ll = long long;
struct Fenwick {
  int N;
  vector<ll> dat;

 public:
  Fenwick(int n) : N(n), dat(N){};
  void add(int p, int x) {
    p++;
    while (p <= N) {
      dat[p - 1] += x;
      p += (p & -p);
    }
  }
  int query(int r) {
    int res = 0;
    while (r > 0) {
      res += dat[r - 1];
      r -= (r & -r);
    }
    return res;
  }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> p(n), s(n), b(n), inc(m), pref(m);
  for (int i = 0; i < n; i++) cin >> p[i];
  for (int i = 0; i < n; i++) cin >> s[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < m; i++) cin >> inc[i];
  for (int i = 0; i < m; i++) cin >> pref[i];
  vector<int> idxp(n);
  iota(idxp.begin(), idxp.end(), 0);
  sort(idxp.begin(), idxp.end(),
       [&](int lhs, int rhs) { return p[lhs] < p[rhs]; });
  vector<int> idxs(n);
  iota(idxs.begin(), idxs.end(), 0);
  sort(idxs.begin(), idxs.end(),
       [&](int lhs, int rhs) { return s[lhs] < s[rhs]; });
  vector<int> idxi(m);
  iota(idxi.begin(), idxi.end(), 0);
  sort(idxi.begin(), idxi.end(),
       [&](int lhs, int rhs) { return inc[lhs] < inc[rhs]; });
  Fenwick t1(n);
  Fenwick t2(n);
  vector<int> idxbp(n);
  iota(idxbp.begin(), idxbp.end(), 0);
  sort(idxbp.begin(), idxbp.end(),
       [&](int lhs, int rhs) { return b[lhs] + p[lhs] > b[rhs] + p[rhs]; });
  vector<int> idxbpi(n);
  for (int i = 0; i < n; i++) idxbpi[idxbp[i]] = i;
  vector<int> idxbmp(n);
  iota(idxbmp.begin(), idxbmp.end(), 0);
  sort(idxbmp.begin(), idxbmp.end(),
       [&](int lhs, int rhs) { return -b[lhs] + p[lhs] > -b[rhs] + p[rhs]; });
  vector<int> idxbmpi(n);
  for (int i = 0; i < n; i++) idxbmpi[idxbmp[i]] = i;
  int cnt = 0;
  auto insert = [&](int x) {
    cnt++;
    t1.add(idxbpi[x], 1);
    t2.add(idxbmpi[x], 1);
  };
  auto erase = [&](int x) {
    cnt--;
    t1.add(idxbpi[x], -1);
    t2.add(idxbmpi[x], -1);
  };
  auto calc = [&](int x) {
    int lb = -1, ub = n;
    while (ub - lb > 1) {
      int mid = (lb + ub) / 2;
      if (b[idxbp[mid]] + p[idxbp[mid]] > inc[x] + pref[x])
        lb = mid;
      else
        ub = mid;
    }
    int res = cnt;
    res -= t1.query(lb + 1);
    lb = -1, ub = n;
    while (ub - lb > 1) {
      int mid = (lb + ub) / 2;
      if (-b[idxbmp[mid]] + p[idxbmp[mid]] > inc[x] - pref[x])
        lb = mid;
      else
        ub = mid;
    }
    res -= t2.query(lb + 1);
    return res;
  };
  vector<ll> res(m);
  int idp = 0;
  int ids = 0;
  for (int i = 0; i < m; i++) {
    int pid = idxi[i];
    while (idp < n && p[idxp[idp]] <= inc[pid]) {
      insert(idxp[idp++]);
    }
    while (ids < n && s[idxs[ids]] < inc[pid]) {
      erase(idxs[ids++]);
    }
    res[pid] = calc(pid);
  }
  for (int i = 0; i < m; i++) cout << res[i] << (i + 1 == n ? "\n" : " ");
  return 0;
}