题目内容

在 Transformer 的 Attention 计算中，为降低长序列的内存开销，常采用 FlashAttention 分块流式计算。每个序列块维护局部状态三元组 $(mx, wd, sv)$，其中：

• $mx$：当前块内所有 $q \cdot k_j$ 的最大值；
• $wd$：重缩放后的权重和 $\sum \exp(q \cdot k_j - mx)$；
• $sv$：重缩放后的加权和 $\sum \exp(q \cdot k_j - mx) \cdot v_j$。

该块的注意力结果为 $attn = sv / wd$。

相邻两块状态 $A=(mx_A, wd_A, sv_A)$ 与 $B=(mx_B, wd_B, sv_B)$ 按顺序合并为 $C=(mx_C, wd_C, sv_C)$：

合并运算满足结合律，可按任意括号顺序得到相同结果。

现给定按顺序排列的 $B$ 个块，第 $i$ 块初始状态为 $(mx_i, wd_i, sv_i)$。需处理 $Q$ 次操作：

1. 单点更新：将第 $i$ 块状态替换为新的 $(mx, wd, sv)$；
2. 区间查询：给定 $[l, r]$，将第 $l$ 到第 $r$ 块依次合并，输出合并后的 $sv_C / wd_C$。

输入描述

第一行：两个整数 $B$、$Q$，分别表示块数与操作数。

接下来 $B$ 行：每行三个实数 $mx_i\ wd_i\ sv_i$，表示第 $i$ 块的初始状态（$1 \le i \le B$）。

接下来 $Q$ 行：每行描述一次操作：

• 1 i mx wd sv：单点更新第 $i$ 块，无输出；
• 2 l r：查询区间 $[l,r]$ 合并后的注意力结果。

数据范围：

• $1 \le B, Q \le 2 \times 10^5$；
• $-50 \le mx_i, mx \le 50$；
• $0 < wd_i, wd \le 100$；
• $-10^4 \le sv_i, sv \le 10^4$。

提示：涉及指数运算，请使用双精度浮点（double / float），指数函数用标准库 exp()。

输出描述

对每个区间查询操作，输出合并后的注意力结果，保留小数点后 $6$ 位。

样例1

输入

4 6
0.0 2.0 4.0
2.0 1.5 9.0
1.0 3.0 6.0
4.0 2.0 8.0
2 1 4
2 2 2
1 3 0.0 1.0 20.0
2 1 3
2 3 4
2 4 4

输出

4.014241
6.000000
6.426028
4.145195
4.000000

说明

初始四块状态为 $(0,2,4)$、$(2,1.5,9)$、$(1,3,6)$、$(4,2,8)$。

查询 $[1,4]$：四块依次合并，$mx$ 取到 $4.0$，经指数重缩放后 $attn \approx 4.014241$。

查询 $[2,2]$：单块，$9.0/1.5=6.000000$。

将块 3 更新为 $(0,1,20)$ 后，查询 $[1,3]$ 得 $attn \approx 6.426028$；查询 $[3,4]$ 得 $4.145195$；查询 $[4,4]$ 得 $8.0/2.0=4.000000$。

样例2

输入

2 3
1.0 2.0 8.0
1.0 2.0 12.0
2 1 2
2 1 1
2 2 2

输出

5.000000
4.000000
6.000000

说明

两块 $mx$ 均为 $1.0$，合并时缩放因子相同，$[1,2]$ 等价于权重与值直接相加：$attn=(8+12)/(2+2)=5$。单查块 1 得 $4$，单查块 2 得 $6$。