题目描述

在昆虫王国中，每天早晨，居民们都会和公主 Bubi 一起经过一张自助餐桌。桌上按一行摆放着 $N$ 种点心，编号为 $0$ 到 $N-1$。

普通昆虫有一种奇怪的进食习惯，称为“螃蟹式吃法”：它们会先选择某一种点心 $i$，然后依次吃掉编号为

$$i,\ i-1,\ \ldots,\ 0$$

的点心各一个。

公主 Bubi 有一个优势：她可以控制自己什么时候停止进食；如果她不饿，甚至可以完全不吃。也就是说，如果她选择从点心 $i$ 开始，那么她会依次吃点心

$$i,\ i-1,\ i-2,\ \ldots$$

直到她决定以某个点心 $j$ 结束，其中 $j\le i$。因此她实际吃掉的是编号为

$$i,\ i-1,\ \ldots,\ j$$

的连续一段点心。

每天早晨开始时，每只昆虫都有一个用实数表示的能量值。若某只昆虫吃掉一种编号为 $i$ 的点心，那么它的能量会先乘以某个系数 $c_i$，再加上某个系数 $d_i$。也就是说，若吃之前能量为 $x$，则吃之后能量变为

$$c_i x+d_i.$$

每种点心的 $c_i,d_i$ 未知，并且只与点心种类有关。

虽然 Bubi 不知道每一种点心的具体系数，但经过长期观察，她知道了所有完整“螃蟹式吃法”的效果。具体来说，她知道两组实数

$$a_0,a_1,\ldots,a_{N-1}$$

和

$$b_0,b_1,\ldots,b_{N-1},$$

它们的含义如下：如果某只昆虫以初始能量 $x$ 开始，从点心 $i$ 开始按照螃蟹式吃法一直吃到点心 $0$，那么最终能量为

$$a_i x+b_i.$$

现在，对于给定的初始能量 $x$，Bubi 希望最大化自己早餐结束时的能量。她可以选择任意一段连续的下降编号点心来吃，即选择 $i,j$ 满足

$$0\le j\le i<N,$$

吃掉点心

$$i,\ i-1,\ \ldots,\ j,$$

也可以选择什么都不吃。

接下来有 $Q$ 天。对于每一天，给出 Bubi 的初始能量 $x$，你需要求出她早餐结束后能够获得的最大能量。

你的答案允许有误差。若真实答案为 $s$，你的输出为 $t$，则需要满足

$$\frac{|s-t|}{\max(1,|s|)}\le 10^{-6}.$$

输入中的 $a_i,b_i,x$ 都是“小数位数有限”的数，最多有 $4$ 位小数。

实现细节

你需要实现两个函数。

首先实现：

void init(
    int n,
    int q,
    const std::vector<double>& a,
    const std::vector<double>& b
);

该函数会在程序开始时被调用一次。参数含义如下：

• $n$：点心种类数 $N$；
• $q$：询问天数 $Q$；
• $a,b$：题目中描述的 $a_i,b_i$ 数组。

然后实现：

double query(double x);

该函数会被调用恰好 $Q$ 次。参数 $x$ 表示对应一天 Bubi 的初始能量。函数应返回她能够获得的最大最终能量。

你的程序需要包含头文件：

#include "treat.h"

你的代码不应包含 main 函数，也不应从标准输入读取或向标准输出写入。

本地评测器

官方提供了本地评测器 Lgrader.cpp 和头文件 treat.h。本地评测器的输入格式如下。

第一行包含两个整数 $N,Q$。

接下来 $N$ 行，每行包含两个实数 $a_i,b_i$。

接下来 $Q$ 行，每行包含一个实数 $x_i$，表示一次询问的初始能量。

本地评测器会先调用 init，然后依次调用 query，最后按询问顺序输出所有结果。

约束

$$1\le N,Q\le 100000$$ $$1\le |a_i|,|b_i|\le 10^6$$ $$-10^6\le x_i\le 10^6$$

所有输入实数最多有 $4$ 位小数。

子任务

子任务	分值	$N$	$Q$	其他限制
1	5	$\le 100$		无
2		$\le 1000$
3	10	$\le 5000$
4	15	$\le 10000$
5	10	$\le 50000$		$a_i,b_i,x$ 独立均匀随机生成
6	55	$\le 100000$		无

只有通过某个子任务的所有测试，才能获得该子任务的分数。

样例

输入

4 4
1 1
2 1
-4 7
-16 27
-1
1
2
4

输出

43
11
5
11

样例解释

点心 $0$ 会把能量乘以 $1$ 后加 $1$；点心 $1$ 会把能量乘以 $2$ 后加 $0$；点心 $2$ 会把能量乘以 $-2$ 后加 $3$；点心 $3$ 会把能量乘以 $4$ 后减 $5$。

对于四个初始能量，最优选择分别为：

• 当 $x=-1$ 时，吃点心 $3,2,1,0$，最终能量为 $43$；
• 当 $x=1$ 时，吃点心 $3,2,1,0$，最终能量为 $11$；
• 当 $x=2$ 时，吃点心 $1,0$，最终能量为 $5$；
• 当 $x=4$ 时，只吃点心 $3$，最终能量为 $11$。

下发文件

题目会提供头文件 treat.h 和本地评测器 Lgrader.cpp。 @下发文件