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;
namespace mine {
void chmax(int &x, const long long y) { x = (x > y ? x : y); }
void chmin(int &x, const long long y) { x = (x < y ? x : y); }
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
const int INF = 0x3f3f3f3f;
const int MOD = 19930726;
void add(long long &a, long long b) {
  a += b;
  if (a >= MOD) a -= MOD;
  if (a <= -MOD) a += MOD;
}
long long qpower(long long x, int e) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 2e6 + 10;
pair<int, int> all[N];
int ans[N];
pair<int, int> tmp[N];
bool cmp1(pair<int, int> a, pair<int, int> b) {
  return all[a.first].second < all[b.first].second or
         (all[a.first].second == all[b.first].second and a.second < b.second);
}
struct CDQ {
  vector<pair<int, int> > qq;
  bool cmp(pair<int, int> a, pair<int, int> b, int op) {
    return a.first + a.second * op <= b.first + b.second * op;
  }
  void cdq(int l, int r, int op) {
    if (l >= r) return;
    cdq(l, (l + r) / 2, op);
    cdq((l + r) / 2 + 1, r, op);
    int now = l, j = l - 1;
    for (int i = (l + r) / 2 + 1, add = 0; i <= r; i++) {
      while (j + 1 <= (l + r) / 2 and
             cmp(all[qq[j + 1].first], all[qq[i].first], op))
        j++, tmp[now++] = qq[j], add += (qq[j].second == 0);
      tmp[now++] = qq[i];
      if (qq[i].second) ans[qq[i].first] += add;
    }
    while (now <= r) tmp[now++] = qq[++j];
    for (int i = l; i <= r; i++) qq[i] = tmp[i];
  }
  void solve() {
    int n = qq.size();
    sort(qq.begin(), qq.end(), cmp1);
    cdq(0, n - 1, -1);
    sort(qq.begin(), qq.end(), cmp1);
    reverse(qq.begin(), qq.end());
    cdq(0, n - 1, 1);
  }
} cdq[N];
void modify(int x, int l, int r, int fl, int fr, int id) {
  if (l == fl and r == fr) {
    cdq[x].qq.push_back(make_pair(id, 0));
    return;
  }
  if (fr <= (l + r) / 2)
    modify(2 * x, l, (l + r) / 2, fl, fr, id);
  else if (fl > (l + r) / 2)
    modify(2 * x + 1, (l + r) / 2 + 1, r, fl, fr, id);
  else
    modify(2 * x, l, (l + r) / 2, fl, (l + r) / 2, id),
        modify(2 * x + 1, (l + r) / 2 + 1, r, (l + r) / 2 + 1, fr, id);
}
void ask(int x, int l, int r, int pos, int id) {
  cdq[x].qq.push_back(make_pair(id, 1));
  if (l == r) return;
  if (pos <= (l + r) / 2)
    ask(2 * x, l, (l + r) / 2, pos, id);
  else
    ask(2 * x + 1, (l + r) / 2 + 1, r, pos, id);
}
int fl[N], fr[N], lsh[N];
int getnum(int cnt, int num) {
  return lower_bound(lsh + 1, lsh + cnt + 1, num) - lsh;
}
void main() {
  int n = qread(), m = qread();
  for (int i = 1; i <= n; i++) fl[i] = qread(), lsh[i] = fl[i];
  for (int i = 1; i <= n; i++) fr[i] = qread(), lsh[n + i] = fr[i];
  for (int i = 1; i <= n; i++) all[m + i] = make_pair(fl[i], qread());
  for (int i = 1; i <= m; i++) lsh[2 * n + i] = all[i].first = qread();
  for (int i = 1; i <= m; i++) all[i].second = qread();
  sort(lsh + 1, lsh + n + n + m + 1);
  for (int i = 1; i <= n; i++)
    modify(1, 1, n + n + m, getnum(n + n + m, fl[i]), getnum(n + n + m, fr[i]),
           m + i);
  for (int i = 1; i <= m; i++)
    ask(1, 1, n + n + m, getnum(n + n + m, all[i].first), i);
  for (int i = 1; i < N; i++) cdq[i].solve();
  for (int i = 1; i <= m; i++) write1(ans[i]);
}
};  // namespace mine
int main() {
  srand(time(0));
  mine::main();
}