“机器人工业”公司生产用于领土保护的机器人。机器人保护三角形区域——直角等腰三角形,其内向平行于南北和东西方向。
一些土地的所有者购买并在他的领土上设置机器人来保护它。有时,商人想在那片土地上建造办公室,并想知道有多少机器人将守卫它。您将处理这些查询。
输入
第一行包含整数 N — 土地的宽度和高度,以及整数 Q — 要处理的查询数。
接下来的 Q 行包含您需要处理的查询。
两种类型的查询:
1. 1 dir x y len — 添加一个机器人来保护三角形。根据 dir 的值,x、y 和 len 的值代表不同的三角形: dir = 1:三角形由点 (x, y)、(x + len, y)、(x, y + len) 定义 dir = 2:三角形由点 (x, y) 定义, (x + len, y), (x, y - len) dir = 3: 三角形由点定义 (x, y), (x - len, y), (x, y + len) dir = 4: 三角形由点定义(x, y), (x - len, y), (x, y - len)
2. 2 x y — 输出有多少机器人守卫该点(如果该点位于三角形内部或边界上,则机器人守卫该点)
- 1 ≤ N ≤ 5000
- 1 ≤ Q ≤ 105
- 1 ≤ 目录 ≤ 4
- 三角形的所有点都在范围 [1, N] 内
- 所有数字均为正整数
输出
对于每个第二类型查询输出,有多少机器人守卫该点。每个答案都应该在单独的一行中。
示例
输入 #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