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;
void Read(int &val) {
  val = 0;
  char c;
  do {
    c = getchar();
  } while (!isdigit(c));
  while (isdigit(c)) {
    val = val * 10 + c - '0';
    c = getchar();
  }
}
void Write(int val) {
  if (val < 0)
    putchar('-'), Write(-val);
  else if (val < 10)
    putchar('0' + val);
  else
    Write(val / 10), putchar('0' + val % 10);
}
struct dataDish {
  int p, b, s;
  dataDish(){};
  dataDish(int p, int b, int s) : p(p), b(b), s(s){};
};
struct dataPer {
  int inc, pref, id;
  dataPer(){};
  dataPer(int inc, int pref, int id) : inc(inc), pref(pref), id(id){};
};
const int N = 3e5 + 4;
int n, m;
dataDish dish[N];
dataPer per[N];
vector<int> rarX, rarY[2];
void compress() {
  for (int i = 1; i <= n; ++i) rarX.push_back(dish[i].b);
  for (int i = 1; i <= m; ++i)
    rarX.push_back(per[i].pref), rarX.push_back(per[i].pref + 1);
  sort(rarX.begin(), rarX.end());
  rarX.resize(unique(rarX.begin(), rarX.end()) - rarX.begin());
  for (int i = 1; i <= n; ++i) {
    rarY[0].push_back(dish[i].b - dish[i].p);
    rarY[1].push_back(dish[i].b + dish[i].p);
  }
  for (int i = 1; i <= m; ++i) {
    rarY[0].push_back(per[i].pref - per[i].inc);
    rarY[1].push_back(per[i].pref + per[i].inc);
  }
  for (int id = 0; id <= 1; ++id) {
    sort(rarY[id].begin(), rarY[id].end());
    rarY[id].resize(unique(rarY[id].begin(), rarY[id].end()) -
                    rarY[id].begin());
  }
}
int Find_X(int val) {
  return lower_bound(rarX.begin(), rarX.end(), val) - rarX.begin() + 1;
}
int Find_Y(int id, int val) {
  return lower_bound(rarY[id].begin(), rarY[id].end(), val) - rarY[id].begin() +
         1;
}
vector<int> BIT[2][N], order[2][N];
void prepare() {
  compress();
  sort(dish + 1, dish + n + 1,
       [](dataDish u, dataDish v) { return u.s < v.s; });
  sort(per + 1, per + m + 1,
       [](dataPer u, dataPer v) { return u.inc < v.inc; });
  for (int i = 1; i <= n; ++i) {
    int y = Find_Y(0, dish[i].b - dish[i].p);
    for (int x = Find_X(dish[i].b); x <= n + 2 * m; x += x & (-x))
      order[0][x].push_back(y);
    y = Find_Y(1, dish[i].b + dish[i].p);
    for (int x = Find_X(dish[i].b); x > 0; x -= x & (-x))
      order[1][x].push_back(y);
  }
  for (int x = 1; x <= n + 2 * m; ++x)
    for (int id = 0; id <= 1; ++id) {
      order[id][x].push_back(-1);
      sort(order[id][x].begin(), order[id][x].end());
      order[id][x].resize(unique(order[id][x].begin(), order[id][x].end()) -
                          order[id][x].begin());
      BIT[id][x].resize(order[id][x].size());
    }
}
void update_BIT_0(int curX, int curY) {
  for (int x = curX; x <= n + 2 * m; x += x & (-x)) {
    int y = lower_bound(order[0][x].begin(), order[0][x].end(), curY) -
            order[0][x].begin();
    assert(order[0][x][y] == curY);
    for (; y > 0; y -= y & (-y)) BIT[0][x][y]++;
  }
}
int get_BIT_0(int curX, int curY) {
  int ans = 0;
  for (int x = curX; x > 0; x -= x & (-x)) {
    int y = lower_bound(order[0][x].begin(), order[0][x].end(), curY) -
            order[0][x].begin();
    for (; y < (int)BIT[0][x].size(); y += y & (-y)) ans += BIT[0][x][y];
  }
  return ans;
}
void update_BIT_1(int curX, int curY) {
  for (int x = curX; x > 0; x -= x & (-x)) {
    int y = lower_bound(order[1][x].begin(), order[1][x].end(), curY) -
            order[1][x].begin();
    assert(order[1][x][y] == curY);
    for (; y < (int)BIT[1][x].size(); y += y & (-y)) BIT[1][x][y]++;
  }
}
int get_BIT_1(int curX, int curY) {
  int ans = 0;
  for (int x = curX; x <= n + 2 * m; x += x & (-x)) {
    int y = upper_bound(order[1][x].begin(), order[1][x].end(), curY) -
            order[1][x].begin() - 1;
    for (; y > 0; y -= y & (-y)) ans += BIT[1][x][y];
  }
  return ans;
}
int ans[N];
void sol() {
  prepare();
  int point = n;
  for (int i = m; i >= 1; --i) {
    int id = per[i].id;
    while (point > 0 && dish[point].s >= per[i].inc) {
      update_BIT_0(Find_X(dish[point].b),
                   Find_Y(0, dish[point].b - dish[point].p));
      update_BIT_1(Find_X(dish[point].b),
                   Find_Y(1, dish[point].b + dish[point].p));
      --point;
    }
    int x = Find_X(per[i].pref), y = Find_Y(0, per[i].pref - per[i].inc);
    ans[id] += get_BIT_0(x, y);
    x = Find_X(per[i].pref + 1);
    y = Find_Y(1, per[i].pref + per[i].inc);
    ans[id] += get_BIT_1(x, y);
  }
  for (int i = 1; i <= m; ++i) Write(ans[i]), putchar(' ');
  putchar('\n');
}
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
  Read(n);
  Read(m);
  for (int i = 1; i <= n; ++i) Read(dish[i].p);
  for (int i = 1; i <= n; ++i) Read(dish[i].s);
  for (int i = 1; i <= n; ++i) Read(dish[i].b);
  for (int i = 1; i <= m; ++i) Read(per[i].inc);
  for (int i = 1; i <= m; ++i) Read(per[i].pref);
  for (int i = 1; i <= m; ++i) per[i].id = i;
  sol();
  return 0;
}