题目描述

平面上放置了 $n$ 个魔法标记，第 $i$ 个标记最初的坐标为 $(x_i,y_i)$。随后，杰西对这些标记进行 $q$ 次魔术操作。每次操作用五个整数 $l,r,x,y,a$ 描述，其中 $a\in\{90,180,270\}$。杰西将编号从 $l$ 到 $r$ 的所有标记绕点 $(x,y)$ 顺时针旋转 $a$ 度。

每次操作后，为了准备下一次魔术，杰西都需要用一块特殊的矩形布覆盖所有标记。矩形的各边必须与坐标轴平行。请计算每次操作后，能够覆盖所有标记的矩形布的最小面积。

保证每次操作后，所有标记的坐标绝对值均不超过 $10^9$。

输入格式

第一行包含两个整数 $n,q$，满足 $1\le n,q\le 2\cdot10^5$。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，满足 $|x_i|,|y_i|\le10^8$，表示第 $i$ 个标记的初始坐标。

接下来 $q$ 行，每行包含五个整数 $l,r,x,y,a$，满足 $1\le l\le r\le n$、$|x|,|y|\le10^8$、$a\in\{90,180,270\}$，表示一次操作。

输出格式

输出 $q$ 行，每行一个整数，表示相应操作结束后所需矩形布的最小面积。

5 3
1 2
-2 4
3 3
-1 -1
5 -3
1 3 0 0 90
2 3 5 5 180
4 5 -4 -3 180

30
128
360

8 4
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7 8 0 0 270
5 8 0 0 270
3 8 0 0 270
1 8 0 0 270

16
4
1
1

1 3
0 0
1 1 0 0 90
1 1 0 0 180
1 1 0 0 270

0
0
0

3 2
0 0
-1 0
1 0
1 1 -1 -1 180
1 1 -1 -1 180

6
0