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;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T &st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T &st, T v) {
  st = min(st, v);
}
inline void setprec(ostream &out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T *arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T *arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F &f, R &...r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
struct BIT {
  int N, cqid;
  vector<int> bit;
  vector<int> qid;
  void init(int n) {
    N = n;
    bit.resize(N + 1);
    qid.resize(N + 1);
  }
  int &get(int x) {
    if (qid[x] != cqid) {
      qid[x] = cqid;
      bit[x] = 0;
    }
    return bit[x];
  }
  void reset() { cqid++; }
  void add(int x, int v) {
    for (; x <= N; x += x & -x) (get(x)) += (v);
  }
  int sum(int x) {
    int sum = 0;
    for (; x; x -= x & -x) (sum) += (get(x));
    return sum;
  }
};
struct Rank {
  vector<int> rank;
  void add(int x) { rank.push_back(x); }
  void init() {
    sort(rank.begin(), rank.end());
    rank.resize(unique(rank.begin(), rank.end()) - rank.begin());
  }
  int get(int x) {
    return lower_bound(rank.begin(), rank.end(), x) - rank.begin() + 1;
  }
};
struct person {
  int x, y, i;
};
struct dish {
  int x, yl, yr;
};
void rot45Set(int &x, int &y) {
  int a = x + y, b = -x + y;
  x = a;
  y = b;
}
pii rot45(int &x, int &y) {
  pii res = make_pair(x, y);
  rot45Set(res.first, res.second);
  return res;
}
struct evt {
  char type;
  int x, y, ind;
};
const int MN = 1e5 + 1;
int N, M;
dish dishes[MN];
person people[MN];
Rank compy;
vector<evt> events;
int ans[MN];
BIT bit;
void CDQ(int L, int R, vec<evt> events) {
  if (L > R) return;
  if (events.empty()) return;
  int mid = ((ll)L + (ll)R) / 2;
  vec<evt> lhs, rhs;
  bit.reset();
  for (auto &e : events) {
    if (e.type == 'Q') {
      if (R <= e.x)
        ans[e.ind] += bit.sum(e.y);
      else if (L < R) {
        if (e.x > mid) rhs.push_back(e);
        lhs.push_back(e);
      }
    } else {
      if (e.type == 'A')
        bit.add(e.y, 1);
      else if (e.type == 'D')
        bit.add(e.y, -1);
      if (L < R) {
        if (e.x <= mid)
          lhs.push_back(e);
        else
          rhs.push_back(e);
      }
    }
  }
  CDQ(L, mid, lhs);
  CDQ(mid + 1, R, rhs);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  scan(N, M);
  for (__typeof(0) i = 0; i < N; i++) scan(dishes[i].yl);
  for (__typeof(0) i = 0; i < N; i++) scan(dishes[i].yr);
  for (__typeof(0) i = 0; i < N; i++) scan(dishes[i].x);
  for (__typeof(0) i = 0; i < M; i++) scan(people[i].y);
  for (__typeof(0) i = 0; i < M; i++) scan(people[i].x);
  for (__typeof(0) i = 0; i < M; i++) people[i].i = i;
  sort(people, people + M,
       [](const person &a, const person &b) { return a.y < b.y; });
  sort(dishes, dishes + N,
       [](const dish &a, const dish &b) { return a.yr < b.yr; });
  for (__typeof(0) i = 0; i < N; i++) {
    auto &d = dishes[i];
    events.push_back({'A', d.x, d.yl, -1});
  }
  int ptr = 0;
  for (__typeof(0) i = 0; i < M; i++) {
    while (ptr < N && dishes[ptr].yr < people[i].y) {
      auto &d = dishes[ptr];
      events.push_back({'D', d.x, d.yl, -1});
      ptr++;
    }
    auto &p = people[i];
    events.push_back({'Q', p.x, p.y, p.i});
  }
  int mn = INT_MAX, mx = INT_MIN;
  for (auto &e : events) {
    rot45Set(e.x, e.y);
    compy.add(e.y);
  }
  compy.init();
  for (auto &e : events) {
    e.y = compy.get(e.y);
    mina(mn, e.x);
    maxa(mx, e.x);
  }
  bit.init(compy.rank.size());
  CDQ(mn, mx, events);
  for (__typeof(0) i = 0; i < M; i++) print(ans[i], ' ');
  print('\n');
  return 0;
}