给你一个文本数据集。你的任务是训练大语言模型（LLM）并找到最小的可能损失。不骗你。

文本数据集是一个文本数组 $t_1, t_2, \dots, t_n$。每个文本 $t_i$ 是一个 token 序列。我们定义 token 集合 $T$ 为在至少一个文本 $t_i$ 中出现的所有 token 的集合。此外，对于每个文本 $t_i$，存在一个位置集合 $L_i \subseteq \{1, 2, \dots, |t_i|\}$。如果 $j \in L_i$，则 token $t_i[j]$ 是由 LLM 生成的；如果 $j \notin L_i$，则是由用户书写的。

我们将上下文大小为 $k$ 的 LLM 定义为一个概率模型 $P_k$，它根据上下文 $w$（一个长度在 $0$ 到 $k$ 之间（含）且元素来自 $T$ 的序列）来定义序列中下一个 token 的概率分布。因此，概率模型 $P_k$ 是一个庞大的概率表 $P_k(\text{next}|w)$，对任意上下文 $w \in T^*$ 且 $0 \le |w| \le k$，以及任意 token $\text{next} \in T$ 都有定义。必须满足条件 $0 \le P_k(\text{next}|w) \le 1$ 且 $\sum_{\text{next} \in T} P_k(\text{next}|w) = 1$。

上下文大小为 $k$ 的 LLM 的损失函数是为 $P_k$ 定义的如下函数：

$$L_k(P_k) = \sum_{i=1}^n \sum_{j \in L_i} -\log_2 P_k \left( \underbrace{t_i[j]}_{\text{next token}} \;\middle|\; \underbrace{t_i[\max(1, j-k) \dots j-1]}_{\text{context}} \right)$$

这里 $t_i[l \dots r] = t_i[l]t_i[l+1]\dots t_i[r]$ 是从第 $l$ 个到第 $r$ 个 token 的子串，$t_i[1 \dots 0]$ 是空字符串。因此，对于每个文本以及每个由 LLM 生成的 token，我们根据前 $k$ 个 token 的子串（如果长度小于 $k$，则为整个前缀）作为上下文，将该 token 被生成的概率的负对数（以 2 为底）累加到损失中。如果概率为零，我们假设其负对数为 $+\infty$。该损失函数被称为在 LLM 生成位置上的（以 2 为底的）交叉熵损失（Cross Entropy Loss）。损失函数值 $L_k(P_k)$ 越小，LLM $P_k$ 的效果越好。

对于每个 $0 \le k < \max_{i=1\dots n} |t_i|$，计算对于某种上下文大小为 $k$ 的 LLM $P_k$ 所能得到的最小可能损失 $L_k(P_k)$。可以证明，该最小值是可达的且不是无穷大。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$) —— 数据集中的文本数量。接下来是文本的描述。

第 $i$ 个文本描述的第一行包含一个整数 $m_i$ ($1 \le m_i \le 3 \cdot 10^5$) —— $t_i$ 的长度 ($m_i = |t_i|$)。

下一行包含 $m_i$ 个字符串 $t_i[1], t_i[2], \dots, t_i[m_i]$ ($1 \le |t_i[j]| \le 5$) —— 文本 $t_i$ 的 token。每个 token 由 ASCII 码在 33 到 126 之间的字符（可打印字符）组成。

下一行包含一个由 $m_i$ 个字母 U 和 L 组成的字符串 $\ell_i$，用于编码集合 $L_i$。所有带有字母 L 的位置均由 LLM 生成，所有带有字母 U 的位置均由用户书写。因此 $L_i = \{j \mid \ell_i[j] = \text{L}\}$。

保证最后一个 token 是由 LLM 生成的，即 $\ell_i[m_i] = \text{L}$。

保证所有 $i$ ($1 \le i \le n$) 的 $m_i$ 之和不超过 $3 \cdot 10^5$。

输出格式

输出 $M = \max_{i=1\dots n} m_i$ 个实数：对于每个 $k = 0, 1, \dots, M - 1$，输出所有可能的上下文大小为 $k$ 的 LLM $P_k$ 的最小可能损失 $L_k(P_k)$。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确；形式化地，设你的答案为 $p$，裁判答案为 $q$，则应满足：$\frac{|p-q|}{\max\{1,|q|\}} \le 10^{-6}$。

样例

输入样例 1

4
5
1 + 1 = 2
UUUUL
5
1 + 2 = 3
UUUUL
5
2 + 1 = 3
UUUUL
5
2 + 2 = 4
UUUUL

输出样例 1

6.000000000000
6.000000000000
4.000000000000
4.000000000000
0.000000000000

输入样例 2

4
4
N E F <EOS>
LLLL
5
N E R C <EOS>
LLLLL
6
N E E R C <EOS>
LLLLLL
5
I C P C <EOS>
LLLLL

输出样例 2

55.683674395584
12.490224995673
8.000000000000
8.000000000000
8.000000000000
8.000000000000

输入样例 3

1
16
a b a c a b a d b a b d a b a c
ULLULLLLLLULLLLL

输出样例 3

22.595941331507
12.464393446710
5.245112497837
2.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000

输入样例 4

2
4
WA WA WA AC
LULL
4
AC AC WA AC
LLUL

输出样例 4

5.509775004327
4.754887502163
4.000000000000
2.000000000000