Robots protection

题意翻译

- 你需要在平面直角坐标系上进行 $q$ 次操作。 - 每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。 - 每个等腰直角三角形可以用四个参数 $dir,x,y,len$ 确定，其中 $dir \in [1,4]$ 表示三角形的方向，$(x,y)$ 表示直角的顶点坐标，$len$ 表示直角边的长度。 - 保证所有点的坐标都是整数且 $\in [1,n]$。 - $n \le 5 \times 10^3$，$q \le 10^5$。

题目描述

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.

输入输出格式

输入格式

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<=10^{5} $ - $ 1<=dir<=4 $ - All points of triangles are within range $ [1,N] $ - All numbers are positive integers

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
2
2
0
1