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 maxn = 100000 + 5;
int n, m;
struct Element {
  int p, s, b;
  int inc, pref;
  int id, l, r, x;
} a[maxn * 2];
int vec[maxn * 3], sz;
int id[maxn * 2];
int c[maxn * 3];
int ret[maxn];
bool cmp1(const Element &a, const Element &b) {
  int x = (a.x ? a.inc + a.pref : a.p + a.b);
  int y = (b.x ? b.inc + b.pref : b.p + b.b);
  if (x != y) return x < y;
  return a.x < b.x;
}
bool cmp2(const Element &a, const Element &b) {
  int x = (a.x ? a.inc - a.pref : a.p - a.b);
  int y = (b.x ? b.inc - b.pref : b.p - b.b);
  if (x != y) return x < y;
  return a.x < b.x;
}
bool cmp_id1(int i, int j) {
  int x = (a[i].x ? a[i].pref : a[i].b);
  int y = (a[j].x ? a[j].pref : a[j].b);
  if (x != y) return x > y;
  return a[i].x < a[j].x;
}
bool cmp_id2(int i, int j) {
  int x = (a[i].x ? a[i].pref : a[i].b);
  int y = (a[j].x ? a[j].pref : a[j].b);
  if (x != y) return x < y;
  return a[i].x > a[j].x;
}
void update(int l, int r, int d) {
  for (int i = l; i <= sz; i += i & -i) c[i] += d;
  for (int i = r + 1; i <= sz; i += i & -i) c[i] -= d;
}
int query(int i) {
  int ret = 0;
  for (; i; i -= i & -i) ret += c[i];
  return ret;
}
void cdq1(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq1(l, mid);
  for (int i = l; i <= r; ++i) id[i] = i;
  sort(id + l, id + r + 1, cmp_id1);
  for (int j = l; j <= r; ++j) {
    int i = id[j];
    if (i <= mid && !a[i].x) {
      update(a[i].l, a[i].r, +1);
    }
    if (i > mid && a[i].x) {
      ret[a[i].id - n] += query(a[i].x);
    }
  }
  for (int j = l; j <= r; ++j) {
    int i = id[j];
    if (i <= mid && !a[i].x) {
      update(a[i].l, a[i].r, -1);
    }
  }
  cdq1(mid + 1, r);
}
void cdq2(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq2(l, mid);
  for (int i = l; i <= r; ++i) id[i] = i;
  sort(id + l, id + r + 1, cmp_id2);
  for (int j = l; j <= r; ++j) {
    int i = id[j];
    if (i <= mid && !a[i].x) {
      update(a[i].l, a[i].r, +1);
    }
    if (i > mid && a[i].x) {
      ret[a[i].id - n] += query(a[i].x);
    }
  }
  for (int j = l; j <= r; ++j) {
    int i = id[j];
    if (i <= mid && !a[i].x) update(a[i].l, a[i].r, -1);
  }
  cdq2(mid + 1, r);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].p);
    vec[sz++] = a[i].p;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].s);
    vec[sz++] = a[i].s;
  }
  for (int i = 0; i < n; ++i) scanf("%d", &a[i].b);
  for (int i = n; i < n + m; ++i) {
    scanf("%d", &a[i].inc);
    vec[sz++] = a[i].inc;
  }
  for (int i = n; i < n + m; ++i) scanf("%d", &a[i].pref);
  sort(vec, vec + sz);
  sz = unique(vec, vec + sz) - vec;
  for (int i = 0; i < n; ++i) {
    a[i].l = lower_bound(vec, vec + sz, a[i].p) - vec + 1;
    a[i].r = lower_bound(vec, vec + sz, a[i].s) - vec + 1;
  }
  for (int i = n; i < n + m; ++i) {
    a[i].x = lower_bound(vec, vec + sz, a[i].inc) - vec + 1;
  }
  for (int i = 0; i < n + m; ++i) a[i].id = i;
  sort(a, a + n + m, cmp1);
  cdq1(0, n + m - 1);
  sort(a, a + n + m, cmp2);
  cdq2(0, n + m - 1);
  for (int i = 0; i < m; ++i) printf("%d%c", ret[i], " \n"[i == m - 1]);
  return 0;
}