题目背景

古神线段树太难了，出题人做不出来，于是改了一下。

题目描述

• 一条直线表示为 $(sx, sy, tx, ty)$，保证 $sx \not= tx$。
• 一条直线的出现，会点亮所有整点 $(x, y)$，满足：$$y \cdot (tx-sx) \cdot \big( (ty-sy)\cdot(x-sx) - (tx-sx)\cdot(y-sy) \big) \ge 0$$
• 一个已经被点亮的点不会熄灭，也不会被点亮第二次。

有 $n$ 次操作。一次操作可能为：

1. 添加一条直线。
2. 查询在一个矩形区间内被点亮的点数。

每个测试点包含多组测试数据。

输入格式

第一行两个正整数 $c,T$，表示测试点编号和数据组数。在样例中，$c$ 为最小的满足对应性质的测试点编号。

对于每组数据：

• 第一行包含一个正整数 $n$，表示操作次数。

• 接下来 $n$ 行，每行包含 $5$ 个整数，表示一个操作，具体如下：

  • 1 sx sy tx ty：添加一条直线。
  • 2 lx ly rx ry：询问满足 $lx{\le}x{\le}rx$ 且 $ly{\le}y{\le}ry$ 的被点亮的点数。

输出格式

对于每个操作 $2$，在一行内输出一个数表示答案。

1 1
3
1 1 2 4 1
1 4 4 2 1
2 1 1 4 3

8

提示

本题输入量较大，下发文件中提供一份快读模板。

对于所有的数据：

• $1 \le n \le 1\times 10^6$；
• $1 \le \sum n \le 2\times 10^6$；
• $-10^9 \le sx,sy,tx,ty \le 10^9$，$sx \not= tx$；
• $-10^9 \le lx \le rx \le 10^9$，$-10^9 \le ly \le ry \le 10^9$。

::cute-table{tuack}

测试点编号	$n \leq$	$\sum n \leq$	特殊性质
$1$	$100$	$500$	A
$2$	$1\times 10^6$	$2\times 10^6$	B
$3$	^		C
$4$			D
$5$	$1\times 10^5$	$3\times 10^5$	无
$6\sim 10$	$1\times 10^6$	$2\times 10^6$	^

• 特殊性质 A：保证 $\lvert lx \rvert,\lvert rx \rvert,\lvert ly \rvert,\lvert ry \rvert \le 500$。
• 特殊性质 B：保证 $lx=rx$。
• 特殊性质 C：保证 $sx=0,sy=0$。
• 特殊性质 D：保证 $ly=-1e9, ry=1e9$。