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, id[maxn * 2], c[maxn * 3], ret[maxn];
bool cmp1(Element X, Element Y) {
  int x = (X.x ? X.inc + X.pref : X.p + X.b);
  int y = (Y.x ? Y.inc + Y.pref : Y.p + Y.b);
  if (x != y) return x < y;
  return X.x < Y.x;
}
bool cmp2(Element X, Element Y) {
  int x = (X.x ? X.inc - X.pref : X.p - X.b);
  int y = (Y.x ? Y.inc - Y.pref : Y.p - Y.b);
  if (x != y) return x < y;
  return X.x < Y.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 dlt) {
  for (int i = l; i <= sz; i += i & -i) c[i] += dlt;
  for (int i = r + 1; i <= sz; i += i & -i) c[i] -= dlt;
}
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 == 0) update(a[i].l, a[i].r, +1);
    if (i > mid && a[i].x != 0) 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 == 0) update(a[i].l, a[i].r, +1);
    if (i > mid && a[i].x != 0) 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 ", ret[i]);
  return 0;
}