AT_arc008_4 [ARC008D] タコヤキオイシクナール

在章鱼烧店因试吃活动而获成功后，兴奋的高桥社长决定将业务扩展至全国，并计划在工厂中批量生产冷冻章鱼烧。为此，他购置了一台机器，名为“Takoyaki Oishikunar”。这台设备由 $N$ 个盒子连成通道状结构，每个盒子通过传送带首尾相连。第 $i$ 个盒子的出口直通第 $i+1$ 个盒子的入口。 每个盒子标有一对实数 $(a, b)$，当一个美味度为 $r$ 的章鱼烧通过时，其美味度将变为 $a \times r + b$。例如，若美味度为 $1$ 的章鱼烧经过一个标有 $(2, 1)$ 的盒子，美味度将变为 $3$，然后继续通过一个标有 $(-1, 2)$ 的盒子，最终美味度将为 $-1$。 起初，每个盒子上的数字均为 $(1, 0)$，因此章鱼烧经过所有盒子后美味度并不会改变。你决定依次将美味度为 $1$ 的章鱼烧投入机器中。然而，高桥社长在 $M$ 次实验中改动了盒子上的数字。请你计算出最终制成的章鱼烧的美味度可能的最小值和最大值。 注意，“Takoyaki Oishikunar”一次只能处理一个章鱼烧，并在加工期间盒子上的数值不会被改变。高桥社长可以在当前章鱼烧加工结束和下一个章鱼烧开始加工之间，选择性地修改一个盒子的参数。 ### 输入格式 ``` N M p_0 a_0 b_0 p_1 a_1 b_1 ... p_{M-1} a_{M-1} b_{M-1} ``` - 第一行有两个正整数 $N$ 和 $M$，分别表示盒子的数量和高桥社长修改盒子数字的次数。 - 接下来的 $M$ 行，每行有三个数：盒子编号 $p_i\ (1 \le p_i \le N)$、修改后的数值 $a_i\ (-1 \le a_i \le 1)$ 和 $b_i\ (-1 \le b_i \le 1)$。 ### 输出格式 输出两行，每行一个实数： - 第一行输出最终制成的章鱼烧的美味度的最小值。 - 第二行输出其最大值。 ### 数据范围与提示 - 对于 small 数据集：$1 \le N \le 1,000$，$0 \le M \le 1,000$ - 对于 large 数据集：$1 \le N \le 10^{12}$，$0 \le M \le 100,000$ - 输出允许绝对误差或相对误差小于等于 $10^{-6}$。 **本翻译由 AI 自动生成**

无

无