题目背景

题目背景部分是本题所用记号的约定。（对映射、排列比较熟悉的选手可以略过这一部分）

记小写字母集合 $\{\mathtt{a},\dots, \mathtt{z}\}$的一个子集为 $\mathbb L$，一个字符串 $S$ 的第 $i$ 个字符为 $S[i]$。

定义在 $\mathbb L$ 上的映射为一个双射 $f: \mathbb L \rightarrow \mathbb L$，字符 $s$ 在 $f$ 下的像为 $f(s)$。我们可以将一个映射 $f$ 记为一个长度为 $|\mathbb L|$ 的排列 $f$，令第 $i$ 个字母被映射为第 $f_i$ 个字母。一个恒等映射为满足所有字母被映射到其本身的映射。（为方便，前述排列均为 $0 \sim |\mathbb L| - 1$ 的排列）

定义映射 $f$ 对字符串 $S$ 的操作 $f(S)$ 为将字符串内每个元素 $S[i]$ 替换为 $f(S[i])$。例如，当 $\mathbb L = \{\mathtt{a},\mathtt{b},\mathtt{c}\}$，$f = \{ 1,2,0 \}$，$S = \mathtt{abcac}$ 时，$f(S) = \mathtt{bcaba}$ 。

定义映射的复合运算 $\circ$ 按如下方式给出 $c = a\circ b$：

$$\forall\ s\in \mathbb{L},\ c(s) = b(a(s))$$

例如，当 $\mathbb L = \{\text{a},\text{b},\text{c}\}$，$f = \{ 1,2,0 \}$，$g = \{ 0,2,1 \}$ 时，存在 $h = f\circ g = \{2,1,0\}$ 满足条件。

对确定的 $a,b$，只存在一个 $c$ 满足条件。

题目描述

给定 $\mathbb L$ 的大小 $l$，$\mathbb L = \{$ 前 $l$ 个小写字母 $\}$。

给定循环节大小为 $n$ 的无限长操作序列与 $m$ 个映射，第 $i$ 个映射被编号为 $f_i$。你有一个映射 $f_0$，其初始时是恒等映射。

第 $i$ 次操作有两种可能的情况：

1. 为一个数字 $k$，保证 $k \in [1,m]$。

   将 $f_k$ 复合到 $f_0$ 上。
   具体地，我们操作 $f_0 \leftarrow f_0 \circ f_k$。

2. 为一个字符串 $S$，保证其由 $\in \mathbb{L}$ 的元素组成。

   记录下 $f_0(S)$。

现在有 $q$ 次询问，每次询问给定 $x$，你需要输出第 $x$ 次记录下的字符串。

输入格式

为避免大量输入输出带来的时空损耗，本题使用特殊输入方式，真正的输入格式见最后一行。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull n, m, q, l, STR_LEN, seed1, seed2, FREQ, MAX_X;
int f[26], LEN;

ull xorShift128Plus() {
    ull k3 = seed1, k4 = seed2;
    seed1 = k4;
    k3 ^= (k3 << 23);
    seed2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return seed2 + k4;
}

signed main() {
    scanf("%llu %llu %llu %llu %llu %llu %llu %llu %llu", 
            &n, &m, &q, &l, &seed1, &seed2, &STR_LEN, &FREQ, &MAX_X);
    seed1 = xorShift128Plus() * xorShift128Plus();
    seed2 = xorShift128Plus() * xorShift128Plus();
    mt19937 rnd(seed1 * seed2);

    for (int i = 0; i < l; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        shuffle(f, f + l, rnd);
        for (int i = 0; i < l; i++) {
            printf("%d ", f[i]);
        } putchar('\n');
    }

    for (int i = 1; i <= n; i++) {
        if (xorShift128Plus() % FREQ <= 1) {
            printf("%llu ", xorShift128Plus() % m + 1);
        } else {
            LEN = STR_LEN - (xorShift128Plus() & 7);
            for (int i = 1; i <= LEN; i++) {
                printf("%c", (char)(xorShift128Plus() % l + 'a'));
            } putchar(' ');
        } 
    } putchar('\n');

    for (int i = 1; i <= q; i++) {
        printf("%llu\n", xorShift128Plus() % MAX_X + 1);
    }
	return 0;
}

该程序的输出内容为题目描述中的输入，其意义如下：

1. $m$ 行，第 $i$ 行 $l$ 个整数表示第 $i$ 个置换。
2. 一行 $n$ 个字符串或数字表示操作序列。
3. $q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的 $x$。

一行，九个整数 $n, m, q, l, \text{seed1}, \text{seed2}, \text{STR\_LEN}, \text{FREQ}, \text{MAX\_X}$ 。

输出格式

为避免大量输入输出带来的时空损耗，本题使用特殊输出方式。

定义哈希函数 $h(ch)$ 如下：

typedef unsigned long long ull;
ull h(const char ch[]) {
    ull hsh = 0; int len = strlen(ch + 1);
    for (int i = 1; i <= len; i++) hsh = hsh * 131 + ch[i];
    return hsh;
}

设第 $i$ 次输出的字符串为 $S_i$。形式化地，你需要输出

$$\bigoplus_{i = 1}^q \ (h(S_i) - i) \text{ mod } 2^{64} $$

即所有 $h(S_i) - i$ 模 $2^{64}$ 所得值的异或和。

样例 #1

样例输入 #1

10 5 20 10 114514 1919810 10 4 100

样例输出 #1

1303754058526545

样例解释 #1

下面为 $S_i$ 按顺序排列的结果：

feeici
efgae
dgcc
gccfdf
hifch
iccgdg
daahddbd
gfc
bfgdb
dgff
beeabbcb
dgi
dgihd
geefcf
cifjc
gfc
jfgej
jhcc
gbbfef
iacc

样例 #2

样例输入 #2

500000 250000 1000000 26 1232541 4324123 50 6 1000000000000000000

样例输出 #2

1813995060911458432

说明/提示

数据范围

$\textbf{Subtask}$	$n, m\leq$	$q \leq$	$l \leq$	$x \leq$	分数
$1$	$10$	$100$	$10$	$100$	$10$
$2$	$10^3$		$20$	$10^5$	$20$
$3$	$10^5$		$26$	$10^9$	$30$
$4$	$10^6$			$10^{18}$	$40$

对于 $100\%$ 的数据，$1 \leq n, m, q \leq 10^6$，$2 \leq l \leq 26$，$1 \leq x \leq 10^{18}$，$8 \leq \text{STR\_LEN} \leq 50$，$1 \leq \text{FREQ} \leq 40$，$\text{seed1, seed2}$ 可通过 unsigned long long 型变量保存。

保证 std 不依赖特殊的输入输出方式实现。