SP12398 LCPC12C - Johnny Listens to Music

Johnny 非常喜欢听音乐。每天他都会根据情况选择在笔记本上添加、删除或收听音乐曲目，具体来说，他可以执行以下操作之一： - 下载一首新曲目。 - 删除最后下载的且尚未被删除的曲目。 - 听他笔记本上已下载的最短曲目。 每个测试用例开始时，Johnny 的曲目列表是空的。每天根据 $R[i] \mod 3$ 的值来决定执行的操作：如果 $R[i] \mod 3 = 0$，他会听当前列表中最短的曲目；如果 $R[i] \mod 3 = 1$，他会删除最后一首未被删除的曲目；如果 $R[i] \mod 3 = 2$，他会下载一首时长为 $R[i]$ 分钟的新曲目。你的任务是计算 Johnny 总共花了多少分钟在听音乐上。 为了使输入更简单，将采用以下方式生成数组 $R$。给定一个数组 $h$，按照下面的伪代码生成数组 $R$： ```plaintext 输入数组: h 输出数组: R (大小为 n) j := 0 m := h 的大小 for i := 0 to n-1 R[i] := h[j] s := (j+1) % m h[j] := ( ( h[j] ^ h[s] ) + 13 ) % 835454957 j := s ``` 这个伪代码和题目的约束条件确保每首曲目的长度在 $0$ 到 $835454956$ 之间（包括边界）。在上述代码中，% 表示取模运算符，^ 表示按位异或运算符。若 $x$ 和 $y$ 是整数，$(x ^ y)$ 表示 $x$ 和 $y$ 的按位异或运算，常见于 C/C++ 和 Java 编程语言中。

输入首先给出测试用例的数量 $T$。随后每个测试用例包含两行，第一行给出两个整数 $n$ 和 $m$，其中 $0 < n \leq 10,000,000$ 为数组 $R$ 的大小，$0 < m \leq 50$ 为数组 $h$ 的大小。第二行给出数组 $h$ 的 $m$ 个整数，满足 $0 \leq h[i] \leq 835454956$。

对于每个测试用例，输出结果格式如下： ``` k. S ``` 其中 $k$ 是测试用例编号（从 1 开始），一个点号后跟一个空格，接着是 Johnny 花在听音乐上的总分钟数 $S$。

- $0 < T \leq 10$ - $0 < n \leq 10,000,000$ - $0 < m \leq 50$ - $0 \leq h[i] \leq 835454956$ **本翻译由 AI 自动生成**