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 std::bitset;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::map;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::string;
using std::stringstream;
using std::vector;
class MyTimer {
 public:
  void reset() {}
  void report() {}
} myTimer;
template <typename A, typename B>
std::ostream &operator<<(std::ostream &cout, const pair<A, B> &x) {
  return cout << "(" << x.first << ", " << x.second << ")";
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
  return a > b ? a = b, true : false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
  return a < b ? a = b, true : false;
}
const int maxN = 100000 + 233;
int n, m;
int a[maxN], b[maxN], c[maxN], d[maxN], e[maxN];
int ans[maxN];
struct Q {
  int t;
  int x, y, L, R;
  Q(int t, int x, int y, int L, int R) : t(t), x(x), y(y), L(L), R(R) {}
  bool operator<(const Q &rhs) const {
    return x != rhs.x ? x < rhs.x : y != rhs.y ? y < rhs.y : t > rhs.t;
  }
};
vector<Q> q, tmp;
void initialize() {
  std::ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  for (int i = 1; i <= n; ++i) cin >> c[i];
  for (int i = 1; i <= m; ++i) cin >> d[i];
  for (int i = 1; i <= m; ++i) cin >> e[i];
  for (int i = 1; i <= n; ++i) {
    q.emplace_back(i, -c[i] + a[i], c[i] + a[i], a[i], b[i]);
  }
  for (int i = 1; i <= m; ++i) {
    q.emplace_back(-i, -e[i] + d[i], d[i] + e[i], d[i], d[i]);
  }
  vector<int> t;
  for (auto &p : q) t.push_back(p.L), t.push_back(p.R);
  std::sort(t.begin(), t.end());
  t.erase(std::unique(t.begin(), t.end()), t.end());
  for (auto &p : q)
    p.L = std::lower_bound(t.begin(), t.end(), p.L) - t.begin() + 1,
    p.R = std::lower_bound(t.begin(), t.end(), p.R) - t.begin() + 1;
  std::sort(q.begin(), q.end());
  tmp.resize(q.size(), Q(0, 0, 0, 0, 0));
}
int C[maxN * 3];
void add(int p, int x) {
  p += 2;
  for (int i = p; i <= n * 2 + m + 5; i += i & -i) C[i] += x;
}
int sum(int p) {
  p += 2;
  int r = 0;
  for (int i = p; i > 0; i -= i & -i) r += C[i];
  return r;
}
void solve(int L, int R) {
  if (L >= R) return;
  int M = (L + R) >> 1;
  solve(L, M);
  solve(M + 1, R);
  int i = L, j = M + 1, qwq = L;
  const auto left = [&](const Q &p) {
    tmp[qwq++] = p;
    if (p.t > 0) add(p.L, 1), add(p.R + 1, -1);
  };
  const auto right = [&](const Q &p) {
    tmp[qwq++] = p;
    if (p.t < 0) ans[-p.t] += sum(p.L);
  };
  while (i <= M && j <= R) {
    if (q[i].y < q[j].y || (q[i].y == q[j].y && q[i].t > 0))
      left(q[i++]);
    else
      right(q[j++]);
  }
  while (i <= M) left(q[i++]);
  while (j <= R) right(q[j++]);
  for (int k = L; k <= M; ++k)
    if (q[k].t > 0) add(q[k].L, -1), add(q[k].R + 1, 1);
  for (int k = L; k <= R; ++k) q[k] = tmp[k];
}
int main() {
  initialize();
  solve(0, (int)q.size() - 1);
  for (int i = 1; i <= m; ++i) printf("%d%c", ans[i], " \n"[i == m]);
  return 0;
}