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;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int p[N], s[N], b[N];
int inc[N], pre[N];
int ans[N];
int tr[N];
vector<int> num;
struct node {
  int p, s, b, id, type, res;
  bool operator<(const node &t) const {
    if (p != t.p) return p < t.p;
    if (s != t.s) return s < t.s;
    if (b != t.b) return b < t.b;
    return type < t.type;
  }
} q[N], w[N];
int find(int x) {
  return lower_bound(num.begin(), num.end(), x) - num.begin() + 1;
}
int lowbit(int x) { return x & -x; }
void add(int x, int c) {
  int i;
  for (i = x; i < N; i += lowbit(i)) {
    tr[i] += c;
  }
}
int sum(int x) {
  int res = 0;
  int i;
  for (i = x; i; i -= lowbit(i)) {
    res += tr[i];
  }
  return res;
}
void cdq(int l, int r) {
  if (l >= r) return;
  int mid = l + r >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int i = l, j = mid + 1, k = 0;
  while (i <= mid && j <= r) {
    if (q[i].s <= q[j].s) {
      if (q[i].type == 1) add(q[i].b, 1);
      w[k++] = q[i++];
    } else
      ans[q[j].id] += sum(q[j].b), w[k++] = q[j++];
  }
  while (i <= mid) {
    if (q[i].type == 1) add(q[i].b, 1);
    w[k++] = q[i++];
  }
  while (j <= r) ans[q[j].id] += sum(q[j].b), w[k++] = q[j++];
  for (i = l; i <= mid; i++)
    if (q[i].type == 1) add(q[i].b, -1);
  for (i = l, j = 0; j < k; i++, j++) q[i] = w[j];
}
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int i, j;
  for (i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (i = 1; i <= n; i++) {
    cin >> s[i];
  }
  for (i = 1; i <= n; i++) {
    cin >> b[i];
  }
  for (i = 1; i <= m; i++) {
    cin >> inc[i];
  }
  for (i = 1; i <= m; i++) {
    cin >> pre[i];
  }
  for (i = 1; i <= n; i++) {
    num.push_back(p[i] - b[i]);
    num.push_back(p[i] + b[i]);
    num.push_back(-s[i]);
    q[i] = {-s[i], p[i] + b[i], p[i] - b[i], 0, 1, 0};
  }
  for (i = n + 1; i <= n + m; i++) {
    num.push_back(inc[i - n] - pre[i - n]);
    num.push_back(-inc[i - n]);
    num.push_back(inc[i - n] + pre[i - n]);
    q[i] = {-inc[i - n],
            inc[i - n] + pre[i - n],
            inc[i - n] - pre[i - n],
            i - n,
            2,
            0};
  }
  sort(num.begin(), num.end());
  num.erase(unique(num.begin(), num.end()), num.end());
  for (i = 1; i <= n + m; i++) {
    q[i].p = find(q[i].p);
    q[i].s = find(q[i].s);
    q[i].b = find(q[i].b);
  }
  n = n + m;
  sort(q + 1, q + 1 + n);
  cdq(1, n);
  for (i = 1; i <= m; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}