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;
int inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
int chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
int chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
int dcmp(T a, T b) {
  return a > b;
}
template <int *a>
int cmp_a(int first, int second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
int tp[100005], first[100005], second[100005], s[100005], w[100005];
int xl[20005], xr[20005];
int ans[100005];
vector<int> Q[100005];
int mxx;
void buildt(int first, int l, int r) {
  chkmax(mxx, first);
  xl[first] = l;
  xr[first] = r;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  buildt(first << 1, l, mid);
  buildt(first << 1 | 1, mid + 1, r);
}
void addx(int first, int l, int r, int id) {
  if (l <= xl[first] && xr[first] <= r) {
    Q[first].push_back(id);
    return;
  }
  if (l <= xr[first << 1]) addx(first << 1, l, r, id);
  if (xl[first << 1 | 1] <= r) addx(first << 1 | 1, l, r, id);
}
void addQ(int r, int first, int id) {
  Q[r].push_back(id);
  if (xl[r] == xr[r]) return;
  if (first <= xr[r << 1])
    addQ(r << 1, first, id);
  else
    addQ(r << 1 | 1, first, id);
}
int n, q;
struct bit {
  int s[5005];
  void init() {
    for (int i = 1; i <= n + 1; ++i) s[i] = 0;
  }
  void add(int first, int second) {
    for (++first; first <= n + 1; first += first & -first) s[first] += second;
  }
  int sum(int first) {
    int second = 0;
    for (++first; first; first ^= first & -first) second += s[first];
    return second;
  }
  int sum(int l, int r) {
    chkmax(l, 0);
    return sum(r) - sum(l - 1);
  }
};
bit s1, s2, s3;
int calc(int id, int rt) {
  return s1.sum(second[id]) +
         s2.sum(second[id] - (first[id] - xl[rt]), second[id]) +
         s3.sum(second[id] - (xr[rt] - first[id]), second[id]);
}
void update(int id, int rt) {
  if (w[id] == 1) {
    int y0 = second[id], yu = (s[id] - (xr[rt] - first[id])) + second[id];
    s1.add(y0, 1);
    s1.add(yu, -1);
    s3.add(yu, 1);
  } else if (w[id] == 2) {
    int yr = second[id], yl = second[id] - (s[id] - (xl[rt] - first[id])) - 1;
    s1.add(yl, 1);
    s1.add(yr + 1, -1);
    s2.add(yl, -1);
  } else if (w[id] == 3) {
    int y0 = second[id], yu = (s[id] - (first[id] - xl[rt])) + second[id];
    s1.add(y0, 1);
    s1.add(yu, -1);
    s2.add(yu, 1);
  } else {
    int yr = second[id], yl = second[id] - (s[id] - (first[id] - xr[rt])) - 1;
    s1.add(yl, 1);
    s1.add(yr + 1, -1);
    s3.add(yl, -1);
  }
}
signed main() {
  read(n, q);
  buildt(1, 1, n);
  for (int i = 1; i <= q; ++i) {
    read(tp[i]);
    if (tp[i] == 1) {
      read(w[i], first[i], second[i], s[i]);
      if (w[i] <= 2)
        addx(1, first[i], first[i] + s[i], i);
      else
        addx(1, first[i] - s[i], first[i], i);
    } else {
      read(first[i], second[i]);
      addQ(1, first[i], i);
    }
  }
  for (int i = 1; i <= mxx; ++i) {
    int upd = 0;
    for (auto j : Q[i])
      if (tp[j] == 1) {
        upd = 1;
        update(j, i);
      } else {
        ans[j] += calc(j, i);
      }
    if (upd) s1.init(), s2.init(), s3.init();
  }
  for (int i = 1; i <= q; ++i)
    if (tp[i] == 2) {
      write(ans[i], '\n');
    }
  return 0;
}