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 read() {
  int f = 1;
  int res = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -f;
  } while (ch < '0' || ch > '9');
  do {
    res = res * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f == 1 ? res : -res;
}
const int N = 200005;
const long long INF = 2000000000000LL;
int n, m;
int p[N], b[N], inc[N], pb[N];
int dish[N], usr[N];
int head[N * 2], to[N * 4], nxt[N * 4], tot;
int match[N * 2], res[N];
bool visited[N * 2];
void addEdge(int u, int v) {
  tot++;
  nxt[tot] = head[u];
  to[tot] = v;
  head[u] = tot;
}
bool check(int x) {
  for (int i = head[x]; i; i = nxt[i]) {
    int j = to[i];
    if (!visited[j]) {
      visited[j] = true;
      if (match[j] == -1 || check(match[j])) {
        match[j] = x;
        match[x] = j;
        return true;
      }
    }
  }
  return false;
}
bool cmpd(int x, int y) { return p[x] < p[y]; }
bool cmpu(int x, int y) { return inc[x] < inc[y]; }
struct Splay {
  int son[N][2], f[N], cou[N], siz[N], key[N];
  int root, sz;
  void clear(int x) {
    son[x][0] = son[x][1] = cou[x] = f[x] = siz[x] = key[x] = 0;
  }
  bool get(int x) { return son[f[x]][1] == x; }
  void update(int x) {
    if (x) {
      siz[x] = cou[x];
      if (son[x][0]) siz[x] += siz[son[x][0]];
      if (son[x][1]) siz[x] += siz[son[x][1]];
    }
  }
  void rotate(int x) {
    int old = f[x], oldf = f[old], whichson = get(x);
    son[old][whichson] = son[x][whichson ^ 1], f[son[old][whichson]] = old;
    son[x][whichson ^ 1] = old, f[old] = x;
    f[x] = oldf;
    if (oldf) {
      son[oldf][son[oldf][1] == old] = x;
    }
    update(old);
    update(x);
  }
  void splay(int x) {
    for (int fa; (fa = f[x]); rotate(x)) {
      if (f[fa]) {
        rotate((get(x) == get(fa)) ? fa : x);
      }
    }
    root = x;
  }
  void insert(int x) {
    if (root == 0) {
      sz++;
      son[sz][0] = son[sz][1] = f[sz] = 0;
      key[sz] = x;
      cou[sz] = siz[sz] = 1;
      root = sz;
      return;
    }
    int now = root, fa = 0;
    while (1) {
      if (x == key[now]) {
        cou[now]++;
        update(now);
        update(fa);
        splay(now);
        break;
      }
      fa = now;
      now = son[now][key[now] < x];
      if (now == 0) {
        sz++;
        f[sz] = fa;
        son[sz][0] = son[sz][1] = 0;
        cou[sz] = siz[sz] = 1;
        son[fa][key[fa] < x] = sz;
        key[sz] = x;
        update(fa);
        splay(sz);
        break;
      }
    }
  }
  int find(int x) {
    int now = root, ans = 0;
    while (1) {
      if (now == 0) return ans;
      if (x < key[now]) {
        now = son[now][0];
      } else {
        ans += (son[now][0] ? siz[son[now][0]] : 0);
        if (x == key[now]) {
          splay(now);
          return ans + cou[now];
        }
        ans += cou[now];
        now = son[now][1];
      }
    }
  }
  int findx(int x) {
    int now = root;
    while (1) {
      if (son[now][0] && x <= siz[son[now][0]]) {
        now = son[now][0];
      } else {
        int temp = (son[now][0] ? siz[son[now][0]] : 0) + cou[now];
        if (x <= temp) return key[now];
        x -= temp;
        now = son[now][1];
      }
    }
  }
  int pre() {
    int now = son[root][0];
    while (son[now][1]) now = son[now][1];
    return now;
  }
  int next() {
    int now = son[root][1];
    while (son[now][0]) now = son[now][0];
    return now;
  }
  void del(int x) {
    int whatever = find(x);
    if (cou[root] > 1) {
      cou[root]--;
      update(root);
      return;
    }
    if (!son[root][0] && !son[root][1]) {
      clear(root);
      root = 0;
      return;
    }
    if (!son[root][0]) {
      int oldroot = root;
      root = son[root][1];
      f[root] = 0;
      clear(oldroot);
      return;
    }
    if (!son[root][1]) {
      int oldroot = root;
      root = son[root][0];
      f[root] = 0;
      clear(oldroot);
      return;
    }
    int leftbig = pre(), oldroot = root;
    splay(leftbig);
    son[root][1] = son[oldroot][1];
    f[son[root][1]] = root;
    clear(oldroot);
    update(root);
    return;
  }
} splay[2];
int main() {
  n = read();
  m = read();
  for (int i = 0; i < n; i++) {
    p[i] = read();
  }
  for (int i = 0; i < n; i++) {
    p[i + n] = read() + 1;
  }
  for (int i = 0; i < n; i++) {
    b[i] = read();
  }
  for (int i = 0; i < m; i++) {
    inc[i] = read();
  }
  for (int i = 0; i < m; i++) {
    pb[i] = read();
  }
  for (int i = 0; i < n * 2; i++) dish[i] = i;
  sort(dish, dish + (n * 2), cmpd);
  for (int i = 0; i < m; i++) usr[i] = i;
  sort(usr, usr + m, cmpu);
  int id = 0;
  for (int i = 0; i < m; i++) {
    int ui = usr[i];
    int in = inc[usr[i]];
    for (; id < n * 2; id++) {
      int idx = dish[id];
      if (p[idx] > in) break;
      if (idx < n) {
        splay[0].insert(p[idx] + b[idx]);
        splay[1].insert(b[idx] + 1 - p[idx]);
      } else {
        idx = idx - n;
        splay[0].del(p[idx] + b[idx]);
        splay[1].del(b[idx] + 1 - p[idx]);
      }
    }
    int l = splay[0].find(in + pb[ui]);
    int r = splay[1].find(pb[ui] - in);
    res[ui] = l - r;
  }
  for (int i = 0; i < m; i++) printf("%d\n", res[i]);
  return 0;
}