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;
struct SPLAY {
  int root = 0, tot = 0;
  struct node {
    int son[2], par;
    int sz, tsz, v;
    void init(int _v = 0, int _sz = 0) {
      v = _v;
      tsz = sz = _sz;
      son[0] = son[1] = par = 0;
    }
  } tr[200005];
  void push_up(int x) {
    tr[x].tsz = tr[x].sz + tr[tr[x].son[0]].tsz + tr[tr[x].son[1]].tsz;
  }
  int chk(int x) { return tr[tr[x].par].son[1] == x; }
  void rot(int x) {
    int y = tr[x].par, z = tr[y].par, k = chk(x), w = tr[x].son[k ^ 1];
    tr[y].son[k] = w;
    tr[w].par = y;
    tr[z].son[chk(y)] = x;
    tr[x].par = z;
    tr[x].son[k ^ 1] = y;
    tr[y].par = x;
    push_up(y);
  }
  void splay(int x, int goal) {
    while (tr[x].par != goal) {
      int y = tr[x].par, z = tr[y].par;
      if (z != goal) {
        if (chk(x) == chk(y))
          rot(y);
        else
          rot(x);
      }
      rot(x);
    }
    if (!goal) root = x;
    push_up(x);
  }
  void insert(int v, int sz) {
    int p = root, ff = 0;
    while (p && tr[p].v != v) {
      ff = p;
      p = tr[p].son[v > tr[p].v];
    }
    if (p) {
      tr[p].sz += sz;
    } else {
      p = ++tot;
      if (ff) tr[ff].son[v > tr[ff].v] = p;
      tr[p].init(v, sz);
      tr[p].par = ff;
    }
    splay(p, 0);
  }
  int count(int v) {
    insert(v, 1);
    int re = tr[tr[root].son[1]].tsz;
    insert(v, -1);
    return re;
  }
} V[2];
int n, m, p[200005], s[200005], b[200005], inc[200005], pref[200005],
    ans[200005];
int cnt = 0, tot = 0;
struct node {
  int v, id, kd;
} A[200005 * 4];
bool cmp(node x, node y) {
  if (x.v == y.v) return x.kd < y.kd;
  return x.v < y.v;
}
void add(int v, int id, int kd) {
  A[++tot].v = v;
  A[tot].id = id;
  A[tot].kd = kd;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]), add(p[i], i, 1);
  for (int i = 1; i <= n; i++) scanf("%d", &s[i]), add(s[i], i, 3);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  for (int i = 1; i <= m; i++) scanf("%d", &inc[i]), add(inc[i], i, 2);
  for (int i = 1; i <= m; i++) scanf("%d", &pref[i]);
  sort(A + 1, A + tot + 1, cmp);
  for (int i = 1; i <= tot; i++) {
    int id = A[i].id;
    if (A[i].kd == 1) {
      cnt++;
      V[0].insert(b[id] + p[id], 1);
      V[1].insert(p[id] - b[id], 1);
    } else if (A[i].kd == 2) {
      ans[id] =
          cnt - V[0].count(inc[id] + pref[id]) - V[1].count(inc[id] - pref[id]);
    } else {
      cnt--;
      V[0].insert(b[id] + p[id], -1);
      V[1].insert(p[id] - b[id], -1);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d ", ans[i]);
}