题目内容

你在同城物流平台负责“运费估计引擎”的开发与维护。平台已经积累了大量历史订单，每条订单记录两个核心数值：运输距离 $x$（单位：$\mathrm{km}$）和成交运费 $y$（单位：元）。系统使用一元线性回归模型 $y = a*x + b$ 来快速估算新订单的运费。

由于市场行情会不断变化，历史订单也会持续新增。你需要实现一个在线学习模块：每当有新的订单样本加入，或收到一次预测查询，都要基于当前已有的全部样本实时维护模型并给出结果。

在一次查询发生时，设当前样本集合为 $(x_i, y_i)$，共 $n$ 条。回归参数 $a$ 和 $b$ 需要使平方误差和

达到最小。查询给定坐标 $x_0$ 时，输出的预测值就是该最优直线在 $x_0$ 处的取值。

为了便于在线计算，维护以下四个统计量：

• $Sx = \sum x_i$
• $Sy = \sum y_i$
• $Sxx = \sum x_i^2$
• $Sxy = \sum x_i * y_i$

当最优解唯一时，直接使用最小二乘公式：

此时查询 $x_0$ 的预测值为：

特殊情况处理如下：

• 如果当前没有样本，即 $n=0$，查询结果固定为 $0.000000$。
• 如果 $n \ge 1$ 但最优解不唯一，这等价于所有样本的 $x$ 都相同。为了保证答案唯一，此时采用常数模型：令 $a=0$，$b$ 等于当前所有 $y$ 的平均值，预测值就是该平均值。

约束条件：

• 操作总数 $Q$ 不超过 $200000$。
• 每次操作中给出的 $x$、$y$、$x_0$ 的绝对值都不超过 $10^6$。
• 保证计算过程中涉及的中间统计量能够用 $64$ 位有符号整数表示。

输入描述

第一行包含一个整数 $Q$，表示操作总数。

接下来 $Q$ 行，每行描述一个操作，格式为以下两种之一：

• ADD x y：新增一条历史样本，其中 $x$ 是运输距离，$y$ 是成交运费。
• QUERY x0：基于当前所有样本进行查询，$x_0$ 是需要预测的距离。

输出描述

对于每个 QUERY 操作，输出一行预测值。结果必须保留固定 $6$ 位小数。

样例1

输入

5
ADD 4 8
ADD 4 12
ADD 4 10
QUERY 4
QUERY -3

输出

10.000000
10.000000

说明

三个样本 $(4,8)$、$(4,12)$、$(4,10)$ 的 $x$ 都等于 4，因此所有样本的 $x$ 相同，最小二乘最优解不唯一。

这种情形下采用常数模型：令 $a=0$，$b$ 取所有 $y$ 的平均值。这里 $b=\frac{8+12+10}{3}=10$。

因此无论查询的 $x_0$ 是多少，预测值都为 $10$。QUERY 4 和 QUERY -3 均输出 10.000000。

样例2

输入

6
ADD 1 2
ADD 2 4
ADD 3 5
ADD 4 7
QUERY 0
QUERY 5

输出

0.500000
8.500000

说明

当前 4 个样本为 $(1,2)$、$(2,4)$、$(3,5)$、$(4,7)$。

统计量为 $n=4$，$Sx=1+2+3+4=10$，$Sy=2+4+5+7=18$，$Sxx=1^2+2^2+3^2+4^2=30$，$Sxy=1\times2+2\times4+3\times5+4\times7=53$。

分母 $nSxx-(Sx)^2=4\times30-10^2=20$，不为 0，所以使用最小二乘公式。斜率 $a=\frac{4\times53-10\times18}{20}=1.6$，截距 $b=\frac{18-1.6\times10}{4}=0.5$。

查询 $x_0=0$ 时，预测值 $\hat y=1.6\times0+0.5=0.5$，输出 0.500000。

查询 $x_0=5$ 时，预测值 $\hat y=1.6\times5+0.5=8.5$，输出 8.500000。