问题描述

由于您的炸酱面店非常繁荣，得益于试吃活动。高兴的社长决定在全国范围内展开业务，因此决定在工厂里生产冷冻炸酱面。高橋社长为生产炸酱面而购买的设备之一是名为“炸酱很特别”的机器。这个“炸酱很特别”的机器由N个呈隧道形状的盒子组成。每个盒子都通过传送带直线连接，并且第i(1≦i≦N-1)个盒子的出口与第(i+1)个盒子的入口相连。每个盒子上写着两个实数(a,b)，当将美味度为r的炸酱面放入盒子时，不可思议的是美味度会变为a×r+b。

图1显示了将炸酱面放入“炸酱很特别”机器的情况。当美味度为1的炸酱面经过标有(2,1)的盒子时，美味度将从1变为2×1+1=3，然后通过下一个标有(-1,2)的盒子时，美味度将从3变为-1。

图：将美味度为1的炸酱面放入“炸酱很特别”机器后的美味度变化

最初，每个盒子上都写着数字(1,0)，意味着即使经过N个盒子，炸酱面的美味度也不会变化。因此，您决定将美味度为1的炸酱面一个一个地放入“炸酱很特别”的机器中。然而，爱恶作剧的高橋社长改变了M次盒子上的数字。如果无法保证美味度，则无法出货。请求出制作好的炸酱面的最小和最大美味度。

另外，“炸酱很特别”机器一次只能加工一份炸酱面，而且在“炸酱很特别”机器加工期间，高橋社长不能更改任何盒子上的数字。换句话说，高橋社长只能在炸酱面制作完成后到您将下一个炸酱面放入“炸酱很特别”的机器之间更改盒子上的数字。此外，假设高橋社长不会更改多个盒子的数字。

输入

从标准输入中以以下格式提供输入。N M

p0 a0 b0

p1 a1 b1

...

p(M-1) a(M-1) b(M-1)

• 输入共有M+1行。

• 第一行包含两个以空格分隔的整数N和M，分别表示连接在一条直线上的盒子数量以及高橋社长更改盒子数字的次数。

• 接下来的M行中提供了高橋社长更改的盒子内容。

• 对于第i+2行($0≦i≦M-1$)，以空格分隔的整数pi($1≦pi≦N$)，表示高橋社长更改的第(i+1)个盒子的编号，以及实数ai($-1≦ai≦1$)和bi($-1≦bi≦1$)，表示更改后的盒子a和b的值。

  • 盒子的编号从1到N依次分配给流过的炸酱面。
  • a和b保留小数点后5位。

部分分

测试数据可包含以下2种测试数据集之一，每个数据集的整数N和M范围如下所示。对于能够正确输出所有属于某个测试数据集的测试数据，即使在其他测试数据集中输出错误，也会给出以下部分分。

• small (50分): $1≦N≦1,000,\\ 0≦M≦1,000$
• large (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