P4254 [JSOI2008] Blue Mary 开公司

Blue Mary 最近在筹备开一家自己的网络公司。由于他缺乏经济头脑，所以先后聘请了若干个金融顾问为他设计经营方案。

万事开头难，经营公司更是如此。开始的收益往往是很低的，不过随着时间的增长会慢慢变好。也就是说，**对于一个金融顾问 $i$，他设计的经营方案中，每天的收益都比前一天高，并且均增长一个相同的量 $P_i$。** 由于金融顾问的工作效率不高，**所以在特定的时间，Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益**。由于 Blue Mary 是很没有经济头脑的，所以他在估算每天的最佳获益时完全不会考虑之前的情况，而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值，例如： 有如下两个金融顾问分别对前四天的收益方案做了设计： | | 第一天 | 第二天 | 第三天 | 第四天 | $P_i$ | | :-: | :-: | :-: | :-: | :-: | :-: | | 顾问 1 | $1$ | $5 $| $9$ | $13$ | $4$ | | 顾问 2 | $2$ | $5$ | $8$ | $11$ | $3$ | 在第一天，Blue Mary 认为最大收益是 $2$（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 $9$ 和 $13$（使用顾问 1 的方案）。而他认为前四天的最大收益是：$2 + 5 + 9 + 13 = 29$。 现在你作为 Blue Mary 公司的副总经理，会不时收到金融顾问的设计方案，也需要随时回答 Blue Mary 对某天的“最大收益”的询问（这里的“最大收益”是按照 Blue Mary 的计算方法）。**一开始没有收到任何方案时，你可以认为每天的最大收益值是 0**。下面是一组收到方案和回答询问的例子： - 询问 $2$，回答 $0$。 - 收到方案：$0\ 1\ 2\ 3\ 4\ 5\ \cdots$ - 询问 $2$，回答 $1$。 - 收到方案：$2\ 2.1\ 2.2\ 2.3\ 2.4\ \cdots$ - 询问 $2$，回答 $2.1$。

无

无

**数据范围** $1 \leq N \leq 10 ^ 5$，$1 \leq T \leq 5\times 10 ^ 4$，$0 < P < 100$，$|S| \leq 10 ^ 5$。 **提示** 本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。