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 maxn = 1e5 + 5;
namespace BIT {
int c[maxn << 1];
void add(const int &p, const int &n, const int &v) {
  for (int i = p; i <= n; i += (i & -i)) c[i] += v;
}
int query(const int &p) {
  int ans = 0;
  for (int i = p; i; i -= (i & -i)) ans += c[i];
  return ans;
}
}  // namespace BIT
int p[maxn], s[maxn], b[maxn], c[maxn], f[maxn];
map<int, int> id;
int trans[maxn << 1];
int x[maxn << 1], y[maxn << 1];
int n, m, cnt = 0;
int ans[maxn];
bool cmp(const int &aa, const int &bb) {
  return (aa <= n ? b[aa] : f[aa - n]) == (bb <= n ? b[bb] : f[bb - n])
             ? aa < bb
             : (aa <= n ? b[aa] : f[aa - n]) < (bb <= n ? b[bb] : f[bb - n]);
}
void work1(const int &l, const int &r) {
  if (l == r) return;
  int mid = l + r >> 1;
  work1(l, mid);
  work1(mid + 1, r);
  int pos = mid + 1;
  for (int i = l; i <= mid; i++)
    if (x[i] > n) {
      for (; pos <= r &&
             (x[pos] <= n ? b[x[pos]] + p[x[pos]]
                          : f[x[pos] - n] + c[x[pos] - n]) <=
                 (x[i] <= n ? b[x[i]] + p[x[i]] : f[x[i] - n] + c[x[i] - n]);
           pos++)
        if (x[pos] <= n) BIT::add(trans[x[pos]], cnt, 1);
      ans[x[i] - n] += BIT::query(trans[x[i]]);
    }
  for (int i = mid + 1; i < pos; i++)
    if (x[i] <= n) BIT::add(trans[x[i]], cnt, -1);
  int pos1 = pos = l, pos2 = mid + 1;
  while (pos1 <= mid && pos2 <= r) {
    if ((x[pos1] <= n ? b[x[pos1]] + p[x[pos1]]
                      : f[x[pos1] - n] + c[x[pos1] - n]) <=
        (x[pos2] <= n ? b[x[pos2]] + p[x[pos2]]
                      : f[x[pos2] - n] + c[x[pos2] - n]))
      y[pos++] = x[pos1++];
    else
      y[pos++] = x[pos2++];
  }
  while (pos1 <= mid) y[pos++] = x[pos1++];
  while (pos2 <= r) y[pos++] = x[pos2++];
  for (int i = l; i <= r; i++) x[i] = y[i];
}
void work2(const int &l, const int &r) {
  if (l == r) return;
  int mid = l + r >> 1;
  work2(l, mid);
  work2(mid + 1, r);
  int pos = l;
  for (int i = mid + 1; i <= r; i++)
    if (x[i] > n) {
      for (; pos <= mid &&
             (x[pos] <= n ? p[x[pos]] - b[x[pos]]
                          : c[x[pos] - n] - f[x[pos] - n]) <=
                 (x[i] <= n ? p[x[i]] - b[x[i]] : c[x[i] - n] - f[x[i] - n]);
           pos++)
        if (x[pos] <= n) BIT::add(trans[x[pos]], cnt, 1);
      ans[x[i] - n] += BIT::query(trans[x[i]]);
    }
  for (int i = l; i < pos; i++)
    if (x[i] <= n) BIT::add(trans[x[i]], cnt, -1);
  int pos1 = pos = l, pos2 = mid + 1;
  while (pos1 <= mid && pos2 <= r) {
    if ((x[pos1] <= n ? p[x[pos1]] - b[x[pos1]]
                      : c[x[pos1] - n] - f[x[pos1] - n]) <=
        (x[pos2] <= n ? p[x[pos2]] - b[x[pos2]]
                      : c[x[pos2] - n] - f[x[pos2] - n]))
      y[pos++] = x[pos1++];
    else
      y[pos++] = x[pos2++];
  }
  while (pos1 <= mid) y[pos++] = x[pos1++];
  while (pos2 <= r) y[pos++] = x[pos2++];
  for (int i = l; i <= r; i++) x[i] = y[i];
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> p[i];
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    id[s[i]] = 0;
  }
  for (int i = 1; i <= n; i++) cin >> b[i];
  for (int i = 1; i <= m; i++) {
    cin >> c[i];
    id[c[i]] = 0;
  }
  for (int i = 1; i <= m; i++) cin >> f[i];
  for (map<int, int>::reverse_iterator it = id.rbegin(); it != id.rend(); it++)
    it->second = ++cnt;
  for (int i = 1; i <= n; i++) trans[i] = id[s[i]];
  for (int i = 1; i <= m; i++) trans[n + i] = id[c[i]];
  for (int i = 1; i <= n + m; i++) x[i] = i;
  sort(x + 1, x + n + m + 1, cmp);
  work1(1, n + m);
  sort(x + 1, x + n + m + 1, cmp);
  work2(1, n + m);
  for (int i = 1; i <= m; i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}