問題文
由于品尝活动,您的章鱼烧店变得非常受欢迎。
高桥社长很高兴,决定开始在工厂生产冷冻章鱼烧,以便扩展到全国。
高桥社长购买了用于章鱼烧生产的机器。 1 有一种机器叫章鱼烧 Oishikunaru。
这个章鱼烧 Oishikunaru 的形状像一个隧道。
它由 N 盒子组成。
每个盒子都通过传送带连接成一条直线,
第i(1≦i≦N-1) 个盒子的出口是
连接到第 i+1 个盒子的入口。
盒子包含 2 实数
写着 (a,b) ,很好吃。
当你添加 r 章鱼烧时,它的味道出奇的美味。 a×r+b 。
図 1 是章鱼烧oishikunar与章鱼烧的插图。
标有
(2,1) 的盒子很好吃。 1 当章鱼烧经过时,美味就变成了 2×1+1=3 然后是以下内容
当您经过标有 (-1,2) 的盒子时
味道变为 3 从 -1 。
图表:美味 1 章鱼烧 1 放在章鱼烧Oishikunaru上时味道的变化
第一个框中写的所有数字都是 (1,0) 章鱼烧是
即使经过 N 盒子后,味道仍然没有改变。
在那里,你可以品尝到美味 1 章鱼烧 1 我决定把它们一一放进章鱼烧大食馆里。
但是框中的数字 M 喜欢恶作剧的高桥社长已经改了。
除非能保证美味,否则我们无法发货。求章鱼烧成品的美味程度的最小值和最大值。
此外,章鱼烧大食也同时上架。 1 只能加工单独的章鱼烧,高桥社长在章鱼烧大鱼丸加工章鱼烧时不会更改任何盒子中的编号。
也就是说,高桥社长可以从章鱼烧完成时开始,直到将下一份章鱼烧放到章鱼烧大餐传送带上为止,更改盒子上的编号。
此外,假设高桥社长在此期间不会更改多个盒子中的号码。
有一条
入力
N M
p_0 a_0 b_0
p_1 a_1 b_1
:
:
p_{M-1} a_{M-1} b_{M-1}
- 输入是 有时您需要的只是 M+1 行。
- 1 行包含一个整数,表示以直线连接的框的数量。 N 和一个代表高桥总裁更改框中数字的次数的整数。 M 用空格分隔。
- 2 从线 M 行包含高桥总裁更改的框中的内容。
- i+2\ (0≦i≦M-1) 高桥社长上线
一个整数,表示 i+1 变化最大的框的编号 p_i\ (1≦p_i≦N),更改该框后。
代表 a 值的实数 a_i\ (-1≦a_i≦1)、b 值的实数 b_i\ (-1≦b_i≦1) 用空格分隔。
- 框中的数字按照章鱼烧的上菜顺序排列。 1 从 N 按顺序列出。
- a_i 和 b_i 是小数位 5 。
部分点
如果某个测试数据集中包含的所有测试数据都能输出正确答案,则即使其他测试数据集输出错误答案,也会如下所示给出部分分数。
- 小( 50 点) : 1≦N≦1,000,\ 0≦M≦1,000
- 大( 50 点) : 1≦N≦10^{12},\ 0≦M≦100,000
出力
输出仅为整数和小数,误差至少为绝对误差和相对误差之一。 10^{−6} 如果低于则可以接受。
请在末尾输出换行符。
入力例 1
1 1 1 1 0
出力例 1
1 1
- 高桥社长更改了号码,但新号码与原来的号码相同,所以味道还是一样。
- 因此,章鱼烧成品的美味在于 1 。
入力例 2
3 2 2 -1 1 2 1 0.5
出力例 2
0 1.5
- 1 第二次改变盒子里的数字后,章鱼烧有多好吃? (-1)×1+1=0 。
- 2 第二次改变盒子里的数字后,章鱼烧有多好吃? 1×1+0.5=1.5 。
入力例 3
4 5 1 -0.8 0.5 2 0.72 -0.21 3 1 0.8 4 0.3 0.4142 3 1 0.8
出力例 3
-0.426 1
- 2 第二次改变盒子里的数字后,章鱼烧有多好吃?-0.426、4 第二次改变盒子里的数字后,章鱼烧有多好吃?0.5264 。
- 但是,1 更改盒内编号之前,章鱼烧的味道是 1 ,所以美味度的最大值为 1 。
入力例 4
10 10 6 0.5674 -1 3 -0.432 0.1235 8 0.92 0 4 -0.673 0.12578 6 0.986 -0.567 1 0.11111 1 10 0.98765 -0.1234 10 0.18543 -0.16532 9 -0.756 0.54849 2 -1 0.74436
出力例 4
-1.175043 1