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 N = 3e5 + 100;
int n, m;
int maxN;
vector<int> v[4 * N], setBuyer[4 * N], setDish[4 * N];
int bit[N];
int rez[N];
struct Dish {
  int price, standard, beauty;
  int idx;
  void show() {
    cout << price << ' ' << standard << ' ' << beauty << ' ' << idx << '\n';
  }
} dish[N], dishCom[N];
struct Buyer {
  int income, prefer;
  void show() { cout << income << ' ' << prefer << '\n'; }
} buyer[N], buyerCom[N];
void read_input() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> dish[i].price;
  for (int i = 1; i <= n; ++i) cin >> dish[i].standard;
  for (int i = 1; i <= n; ++i) cin >> dish[i].beauty;
  for (int i = 1; i <= m; ++i) cin >> buyer[i].income;
  for (int i = 1; i <= m; ++i) cin >> buyer[i].prefer;
}
int compression(int first, vector<int> &compress) {
  int lo = 0, hi = compress.size() - 1, pos = 0;
  while (lo <= hi) {
    int mid = lo + hi >> 1;
    if (compress[mid] <= first) {
      pos = mid;
      lo = mid + 1;
    } else
      hi = mid - 1;
  }
  return pos + 1;
}
void prepare() {
  vector<int> compress;
  for (int i = 1; i <= n; ++i) {
    compress.push_back(dish[i].price);
    compress.push_back(dish[i].standard);
  }
  for (int i = 1; i <= m; ++i) compress.push_back(buyer[i].income);
  sort(compress.begin(), compress.end());
  compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
  maxN = compress.size();
  for (int i = 1; i <= n; ++i) {
    dishCom[i].idx = i;
    dishCom[i].price = compression(dish[i].price, compress);
    dishCom[i].standard = compression(dish[i].standard, compress);
  }
  for (int i = 1; i <= m; ++i) {
    buyerCom[i].income = compression(buyer[i].income, compress);
    v[buyerCom[i].income].push_back(i);
  }
}
void build(int first, int left, int right) {
  if (left == right) {
    setBuyer[first] = v[left];
    return;
  }
  int mid = left + right >> 1;
  build(2 * first, left, mid);
  build(2 * first + 1, mid + 1, right);
  setBuyer[first] = setBuyer[2 * first];
  for (auto ss : setBuyer[2 * first + 1]) setBuyer[first].push_back(ss);
}
void update(int first, int left, int right, int idx) {
  if (left > dishCom[idx].standard || right < dishCom[idx].price) return;
  if (dishCom[idx].price <= left && right <= dishCom[idx].standard) {
    setDish[first].push_back(idx);
    return;
  }
  int mid = left + right >> 1;
  update(2 * first, left, mid, idx);
  update(2 * first + 1, mid + 1, right, idx);
}
pair<int, int> rotation(int first, int second) {
  pair<int, int> B;
  B.first = first - second;
  B.second = first + second;
  return B;
}
void fenwick_update(int first, int val) {
  for (; first < N; first += first & -first) bit[first] += val;
}
int fenwick_get(int first, int tot = 0) {
  for (; first > 0; first -= first & -first) tot += bit[first];
  return tot;
}
void get_answer(vector<int> &setD, vector<int> &setB) {
  vector<pair<pair<int, int>, int> > point;
  vector<int> comp;
  for (auto idx : setD) {
    point.push_back({rotation(dish[idx].price, dish[idx].beauty), 0});
    comp.push_back(point.back().first.first);
    comp.push_back(point.back().first.second);
  }
  for (auto idx : setB) {
    point.push_back({rotation(buyer[idx].income, buyer[idx].prefer), idx});
    comp.push_back(point.back().first.first);
    comp.push_back(point.back().first.second);
  }
  sort(comp.begin(), comp.end());
  comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
  for (int i = 0; i < point.size(); ++i) {
    point[i].first.first = compression(point[i].first.first, comp);
    point[i].first.second = compression(point[i].first.second, comp);
  }
  sort(point.begin(), point.end());
  for (auto ss : point)
    if (!ss.second)
      fenwick_update(ss.first.second, 1);
    else
      rez[ss.second] += fenwick_get(ss.first.second);
  for (auto ss : point)
    if (!ss.second) fenwick_update(ss.first.second, -1);
}
void process(int first, int left, int right) {
  get_answer(setDish[first], setBuyer[first]);
  if (left == right) return;
  int mid = left + right >> 1;
  process(2 * first, left, mid);
  process(2 * first + 1, mid + 1, right);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  read_input();
  prepare();
  build(1, 1, maxN);
  for (int i = 1; i <= n; ++i) update(1, 1, maxN, i);
  process(1, 1, maxN);
  for (int i = 1; i <= m; ++i) cout << rez[i] << ' ';
  return 0;
}