题目描述

公元 2038 年，在经历二战后，人类历史的科技进步水平突飞猛进，同此时刻，从电脑、网际网路以至人工智慧，高超的技术已大幅提升人类的生活水平与社会富裕。

与此同时，CyberLife 公司的革命性发明，仿生人，已经渐渐进入千家万户，它们代替人类进行工作，修路工人、居家保姆、老人看护、大楼保全、销售店员等工作均被仿生人所代替。

各种面向不同工作的仿生人有不同的型号，比如 Kara 的型号为 AX400，面向中低端收入人群的家庭管家。

一日，在 Kara 在做家务，它被命令洗干净一堆盘子，望着凸包形状的盘子，她突发奇想，如果只把凸包中的一部分点拎出来重新建成凸包，那么这个新凸包面积多大呢？

于是她对盘子建立平面直角坐标系，并把上的点根据她心情好坏按某种顺序标号，每次取出所有标号在一段区间中的点，并希望你帮她计算这些点构成的凸包的面积大小。

Kara 并不喜欢浮点数，所以输出的所有点的横纵坐标都为整数，同时你输出时要把答案乘以 $2$ 再四舍五入到整数位后再输出。

保证输入的所有点都在凸包上，没有三点共线，为了方便还保证坐标原点一定在凸包盘子内部。

输入格式

第一行两个正整数 $n, m$ 表示凸包的点数与询问数。

下接 $n$ 行，每行两个整数 $x_i, y_i$ 描述凸包上的一个点。

下接 $m$ 行，每行两个整数 $l_i, r_i$ 描述一次询问，保证 $r_i - l_i + 1 \geq 3$。

输出格式

输出 $m$ 行，每行一个整数表示面积乘以 $2$ 再四舍五入后得到的数。

样例

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

29
15

数据范围与提示

对于全部数据，$n, m \leq 150000, -10^9 \leq x_i, y_i \leq 10^9$。

• 对于 $10 \%$ 的数据满足 $n, m \leq 2000$
• 对于 $30 \%$ 的数据满足 $n, m \leq 50000$
• 对于另 $10 \%$ 的数据满足所有点的标号是按照极角序排序的，即点输入时按凸包逆时针顺序排序