Problem: Company "Robots industries" produces robots for territory protection. Robots protect triangle territories — right isosceles triangles with catheti parallel to North-South and East-West directions.

Owner of some land buys and sets robots on his territory to protect it. From time to time, businessmen want to build offices on that land and want to know how many robots will guard it. You are to handle these queries. 

Input

The first line contains integer N — width and height of the land, and integer Q — number of queries to handle.

Next Q lines contain queries you need to process.

Two types of queries: 

  1. 1 dir x y len — add a robot to protect a triangle. Depending on the value of dir, the values of x, y and len represent a different triangle: 
    * dir = 1: Triangle is defined by the points (x, y), (x + len, y), (x, y + len)
    * dir = 2: Triangle is defined by the points (x, y), (x + len, y), (x, y - len)
    * dir = 3: Triangle is defined by the points (x, y), (x - len, y), (x, y + len)
    * dir = 4: Triangle is defined by the points (x, y), (x - len, y), (x, y - len)
  2. 2 x y — output how many robots guard this point (robot guards a point if the point is inside or on the border of its triangle) 


  * 1 ≤ N ≤ 5000
  * 1 ≤ Q ≤ 105
  * 1 ≤ dir ≤ 4
  * All points of triangles are within range [1, N]
  * All numbers are positive integers 

Output

For each second type query output how many robots guard this point. Each answer should be in a separate line.

Examples

Input

17 10
1 1 3 2 4
1 3 10 3 7
1 2 6 8 2
1 3 9 4 2
2 4 4
1 4 15 10 6
2 7 7
2 9 4
2 12 2
2 13 8


Output

2
2
2
0
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 300005, K = 2400005, E = 3000005;
int tp, n, q, c, e, a, b, z, x, y, tot, toa, tob, toc, tod, toe, ind, ine, fr;
struct node {
  int x, y, z, t;
} na[N], nb[N], nc[N], nd[N], ne[N], nm[N];
int out[N], lc[K], rc[K], fro[K], lt[E], rt[E], now[E];
bool cmpt(node a, node b) { return abs(a.t) < abs(b.t); }
bool cmpa(node a, node b) { return a.x < b.x; }
bool cmpb(node a, node b) { return a.x < b.x; }
bool cmpc(node a, node b) { return a.x > b.x; }
bool cmpd(node a, node b) { return a.x > b.x; }
inline void get(int &a) {
  char c = getchar();
  a = 0;
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) a = a * 10 + c - '0';
}
void add(int &p, int l, int r, int q, int x) {
  if (p == 0) {
    p = ++ine;
    lt[p] = rt[p] = now[p] = 0;
  }
  now[p] += x;
  if (l == r) return;
  if (q <= ((l + r) >> 1))
    add(lt[p], l, ((l + r) >> 1), q, x);
  else
    add(rt[p], ((l + r) >> 1) + 1, r, q, x);
}
void add(int &p, int l, int r, int el, int er, int q, int s, int x) {
  if (!(l <= q && q <= r) || !(el <= s && s <= er)) return;
  if (p == 0) {
    p = ++ind;
    lc[p] = rc[p] = fro[p] = 0;
  }
  add(fro[p], el, er, s, x);
  if (l == r) return;
  if (q <= ((l + r) >> 1))
    add(lc[p], l, ((l + r) >> 1), el, er, q, s, x);
  else
    add(rc[p], ((l + r) >> 1) + 1, r, el, er, q, s, x);
}
int query(int p, int l, int r, int ql, int qr) {
  if (p == 0) return 0;
  if (ql <= l && r <= qr) return now[p];
  int ans = 0;
  if (l <= qr && ql <= ((l + r) >> 1))
    ans += query(lt[p], l, ((l + r) >> 1), ql, qr);
  if (((l + r) >> 1) + 1 <= qr && ql <= r)
    ans += query(rt[p], ((l + r) >> 1) + 1, r, ql, qr);
  return ans;
}
int query(int p, int l, int r, int el, int er, int ql, int qr, int sl, int sr) {
  if (p == 0) return 0;
  ql = max(l, ql);
  qr = min(r, qr);
  sl = max(sl, el);
  sr = min(sr, er);
  if (ql > qr || sl > sr) return 0;
  if (ql <= l && r <= qr) return query(fro[p], el, er, sl, sr);
  int ans = 0;
  if (l <= qr && ql <= ((l + r) >> 1))
    ans += query(lc[p], l, ((l + r) >> 1), el, er, ql, qr, sl, sr);
  if (((l + r) >> 1) + 1 <= qr && ql <= r)
    ans += query(rc[p], ((l + r) >> 1) + 1, r, el, er, ql, qr, sl, sr);
  return ans;
}
void worka(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  worka(l, mid);
  worka(mid + 1, r);
  sort(nm + l, nm + 1 + mid, cmpa);
  sort(nm + 1 + mid, nm + 1 + r, cmpa);
  ind = ine = fr = 0;
  for (int i = l, j = mid + 1; j <= r; j++) {
    while (i <= mid && nm[i].x <= nm[j].x) {
      if (nm[i].t < 0) {
        i++;
        continue;
      }
      add(fr, 1, n, 2, 2 * n, nm[i].y, nm[i].z, 1);
      i++;
    }
    if (nm[j].t < 0)
      out[-nm[j].t] += query(fr, 1, n, 2, 2 * n, 1, nm[j].y, nm[j].z, 2 * n);
  }
}
void workb(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  workb(l, mid);
  workb(mid + 1, r);
  sort(nm + l, nm + 1 + mid, cmpb);
  sort(nm + 1 + mid, nm + 1 + r, cmpb);
  ind = ine = fr = 0;
  for (int i = l, j = mid + 1; j <= r; j++) {
    while (i <= mid && nm[i].x <= nm[j].x) {
      if (nm[i].t < 0) {
        i++;
        continue;
      }
      add(fr, 1, n, -n + 1, n - 1, nm[i].y, nm[i].z, 1);
      i++;
    }
    if (nm[j].t < 0)
      out[-nm[j].t] +=
          query(fr, 1, n, -n + 1, n - 1, nm[j].y, n, nm[j].z, n - 1);
  }
}
void workc(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  workc(l, mid);
  workc(mid + 1, r);
  sort(nm + l, nm + 1 + mid, cmpc);
  sort(nm + 1 + mid, nm + 1 + r, cmpc);
  ind = ine = fr = 0;
  for (int i = l, j = mid + 1; j <= r; j++) {
    while (i <= mid && nm[i].x >= nm[j].x) {
      if (nm[i].t < 0) {
        i++;
        continue;
      }
      add(fr, 1, n, -n + 1, n - 1, nm[i].y, nm[i].z, 1);
      i++;
    }
    if (nm[j].t < 0)
      out[-nm[j].t] +=
          query(fr, 1, n, -n + 1, n - 1, 1, nm[j].y, -n + 1, nm[j].z);
  }
}
void workd(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  workd(l, mid);
  workd(mid + 1, r);
  sort(nm + l, nm + 1 + mid, cmpd);
  sort(nm + 1 + mid, nm + 1 + r, cmpd);
  ind = ine = fr = 0;
  for (int i = l, j = mid + 1; j <= r; j++) {
    while (i <= mid && nm[i].x >= nm[j].x) {
      if (nm[i].t < 0) {
        i++;
        continue;
      }
      add(fr, 1, n, 2, 2 * n, nm[i].y, nm[i].z, 1);
      i++;
    }
    if (nm[j].t < 0)
      out[-nm[j].t] += query(fr, 1, n, 2, 2 * n, nm[j].y, n, 2, nm[j].z);
  }
}
int main() {
  get(n);
  get(q);
  for (int i = 1; i <= q; i++) {
    get(c);
    if (c == 1) {
      get(tp);
      get(a);
      get(b);
      get(z);
      switch (tp) {
        case 1:
          na[++toa] = (node){a, b, a + b + z, i};
          break;
        case 2:
          nb[++tob] = (node){a, b, a - b + z, i};
          break;
        case 3:
          nc[++toc] = (node){a, b, a - b - z, i};
          break;
        case 4:
          nd[++tod] = (node){a, b, a + b - z, i};
          break;
      }
    } else {
      get(x);
      get(y);
      ne[++toe] = (node){x, y, 0, i};
    }
  }
  tot = 0;
  for (int i = 1; i <= toa; i++) nm[++tot] = na[i];
  for (int i = 1; i <= toe; i++)
    nm[++tot] = (node){ne[i].x, ne[i].y, ne[i].x + ne[i].y, -ne[i].t};
  sort(nm + 1, nm + 1 + tot, cmpt);
  worka(1, tot);
  tot = 0;
  for (int i = 1; i <= tob; i++) nm[++tot] = nb[i];
  for (int i = 1; i <= toe; i++)
    nm[++tot] = (node){ne[i].x, ne[i].y, ne[i].x - ne[i].y, -ne[i].t};
  sort(nm + 1, nm + 1 + tot, cmpt);
  workb(1, tot);
  tot = 0;
  for (int i = 1; i <= toc; i++) nm[++tot] = nc[i];
  for (int i = 1; i <= toe; i++)
    nm[++tot] = (node){ne[i].x, ne[i].y, ne[i].x - ne[i].y, -ne[i].t};
  sort(nm + 1, nm + 1 + tot, cmpt);
  workc(1, tot);
  tot = 0;
  for (int i = 1; i <= tod; i++) nm[++tot] = nd[i];
  for (int i = 1; i <= toe; i++)
    nm[++tot] = (node){ne[i].x, ne[i].y, ne[i].x + ne[i].y, -ne[i].t};
  sort(nm + 1, nm + 1 + tot, cmpt);
  workd(1, tot);
  for (int i = 1; i <= toe; i++) printf("%d\n", out[ne[i].t]);
  return 0;
}