题目描述

某数据采集系统按照时间顺序记录了一组数值。每条记录由时间戳 $t$、数值 $v$ 和质量标记 $q$ 组成，其中 $q$ 用于描述该条数据的可信程度：

• $q=0$：有效数据；
• $q=1$：可疑数据；
• $q=2$：无效数据。

现在需要对这 $n$ 条记录完成一次完整的数据处理流程。整个流程依次包括无效值修复、局部异常处理、标准化以及评分计算。

请按照下述规则完成计算，并输出最终结果。

处理规则

一、修复无效数据

首先处理所有满足 $q=2$ 的记录。

对于一条无效记录，根据其前后是否存在有效数据决定处理方式：

• 前后均能找到有效数据时，使用这两个有效数据进行线性插值；
• 只能找到前方有效数据时，使用前方有效数据的值；
• 只能找到后方有效数据时，使用后方有效数据的值；
• 前后均找不到有效数据时，不修改该记录的原值。

完成该步骤后，进入异常值处理。

二、处理局部异常值

设移动窗口大小为 $w$。

对于序列中的每一个数据点 $i$，以 $i$ 为中心，向左、向右最多分别取 $(w-1)/2$ 个数据点，并与数据点 $i$ 一起组成当前窗口。

当 $i$ 靠近序列首部或尾部时，窗口可能超出序列边界。此时只保留实际存在于序列中的数据，因此实际窗口大小允许小于 $w$。

换言之：

• 所有数据点都需要执行一次异常值判断；
• 边界位置不补充额外数据；
• 窗口中的元素必须全部来自原序列的合法下标范围。

在当前窗口内计算均值和标准差，并按照以下规则判断当前数据点是否为异常值：

• 偏差 $=|v-\mu|$，其中$\mu$是窗口均值
• 标准差 $=\sigma$，窗口内
• 如果偏差$>k\cdot\sigma$，则$v=\mu$

如果不满足上述条件，则当前值保持不变。

三、进行 z-score 标准化

使用第二步处理完成后的全部数据计算均值和标准差：

• 均值 $\bar{x}=\frac{1}{n}\sum_{i=1}^{n}v_i$
• 标准差 $s=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(v_i-\bar{x})^2}$
• 标准化值 $z_i=\frac{v_i-\bar{x}}{s}$

由此得到每条记录对应的标准化值 $z_i$。

四、计算最终评分

不同质量标记对应不同的质量权重：

• 质量权重 $p_i=\begin{cases}1,&q_i=0\0.5,&q_i=1\0.25,&q_i=2\end{cases}$

根据质量权重以及数据值的绝对值，计算每条记录在最终评分中的权重：

• 原始值权重 $w_i=\frac{p_i|v_i|}{\sum_{j=1}^{n}p_j|v_j|}$

最终的特征分数为：

• 特征分数 $S=\sum_{i=1}^{n}w_i\cdot|z_i|$

将 $S$ 乘以 100 后进行四舍五入，得到最终需要输出的整数。

输入格式

第一行输入三个整数 $n,w,k$，分别表示：

• 数据记录数量；
• 移动窗口大小；
• 异常值判断时使用的标准差倍数。

随后输入 $n$ 行。

第 $i$ 行包含三个整数 $t_i,v_i,q_i$，分别表示第 $i$ 条记录的时间戳、原始值和质量标记。

输出格式

输出一个整数，表示特征分数 $S$ 乘以 100 并四舍五入后的结果。

样例1

输入：

6 3 2
1 10 0
2 15 2
3 20 0
4 18 0
5 100 0
6 12 0

输出：

152

样例说明

第 2 条记录的质量标记为 $q=2$。它的前后均存在有效数据，因此通过线性插值得到 15。

完成无效数据处理后，序列为：

[10,15,20,18,100,12]

随后使用大小为 3 的移动窗口逐点进行异常检测。各数据点的偏差均没有超过对应窗口标准差的 2 倍，因此这一阶段不会修改序列。

标准化阶段中，序列均值为：

$(\mu=(10+15+20+18+100+12)/6=29.17)$

每个点的 $(z_i=(v_i-\mu)/\sigma)$ 依次为：

-0.60、-0.45、-0.29、-0.35、2.22、-0.54

按照质量标记计算权重时，$q=0$ 对应权重 1，$q=1$ 对应权重 0.5，$q=2$ 对应权重 0.25。

因此分母为：

$(denom=\sum p_i|v_i|=1\times10+0.25\times15+1\times20+1\times18+1\times100+1\times12=163.75)$

每个数据点对最终评分的贡献为：

$(\frac{p_i|v_i|}{denom}\times|z_i|)$

全部贡献相加后得到：

$(S\approx1.518)$

因此 $(S\times100)$ 四舍五入后的结果为 152。

样例2

输入：

3 3 2
1 1 0
2 2 0
3 3 0

输出：

82

样例说明

三条记录均不是无效数据，因此第一步不需要修改任何值。

在异常值处理阶段，没有数据点满足平滑条件，序列仍为：

[1,2,3]

标准化时，均值为 2，标准差为 0.8165，因此：

$z\approx[-1.225,0,1.225]$

由于三条记录的 $q$ 均为 0，所以质量权重 $p$ 均为 1。

$|v|$ 的总和为 6，因此：

$w=[1/6,2/6,3/6]$

最终：

$S\approx(1/6)\times1.225+(2/6)\times0+(3/6)\times1.225\approx0.8165$

乘以 100 并四舍五入后得到 82。

数据范围

• $1\le n\le10000$
• $1\le w\le n$ 且$w$为奇数
• $1\le k\le10$
• $-10^9\le v_i\le10^9$
• $1\le t_i\le10^9$ 且$t_i$严格递增
• $q_i\in{0,1,2}$
• 至少有一条有效数据（$q_i=0$）