火星任务 APOLLO 遭遇了强风暴，宇航员 Mark Watney 在受伤后失踪。指挥官 Melissa 试图营救其余船员，但不得不留下 Mark。指挥官在确信 Mark 遇难后才离开。幸运的是，Mark 幸存了下来，现在独自一人在火星上。与人们想象的不同，Mark 在火星上过得很愉快。这里的风景很美，也没有人来打扰他。

在经历了一段时间的苦难后，Mark 成功联系上了 NASA，并得到了他们的帮助以求生存。他需要独自坚持 4 年，直到下一次火星任务来营救他。Mark 喜欢火星，但他遇到了一些问题。最主要的问题是食物。他有可以维持 5 个月生命的食物储备。由于他是一位伟大的植物学家，Mark 决定在火星上种植农作物。在 NASA 的帮助下，他找到了种植的方法，但还有一个问题。他发现他将要种植农作物的田地是一个二维坐标系下的凸多边形。这块田地包含了一些网格点。田地的单元格是多边形内部和边界上的所有整点（包括顶点）。此外，田地的顶点也是整点。他可以在其中一个单元格中种植农作物，问题在于选择哪一个单元格。

Mark 发现，由于火星上的不同因素，有些单元格种植农作物的速度比其他单元格快。凭借他伟大的科学能力，他找到了一个公式。他用一对整数 $f = (a, b)$ 表示生长因子。对于给定的生长因子 $f = (a, b)$，每个单元格 $(x, y)$ 的生长能力为 $g = a \times x + b \times y$。Mark 想要选择具有最大生长能力的单元格。他可能会多次耕种这块田地，并且每次他可能会遇到不同的生长因子（取决于他耕种田地时的季节）。因此，对于 Mark 将要遇到（或预期遇到）的每一个不同的生长因子，他都想知道他能从田地的单元格中获得的最大生长能力。Mark 把所有信息都发给了 NASA 以寻求帮助。NASA 雇佣了你来帮助他们找出 Mark 对于每个生长因子所能获得的最大单元格生长能力。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$），随后是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$（$3 \le N \le 10,000$）和 $Q$（$1 \le Q \le 100,000$），由空格分隔，其中 $N$ 是表示该田地的凸多边形的顶点数，$Q$ 是 Mark 预期遇到的不同生长因子的数量。接下来的 $N$ 行，每行包含一对整数 $x$ 和 $y$，由空格分隔（$-10^9 \le x, y \le 10^9$），表示顶点的坐标。顶点将按逆时针顺序给出。保证没有三点共线。接下来的 $Q$ 行，每行包含一对整数 $a$ 和 $b$（$-10^9 \le a, b \le 10^9$），由空格分隔，表示一个生长因子。

输出格式

对于每个生长因子，打印一行，表示 Mark 在给定的凸多边形（田地）的单元格中可以获得的该生长因子的最大生长能力。

样例

输入 1

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

输出 1

4
2