AT_KeioPC2025_r.Many Strings

给定一个长度为 $N$ 的字符串 $S$。此外，有 $2 \times 10^5$ 个用为空字符串初始化的字符串 $T_1, T_2, \ldots , T_{200000}$。
请按给定顺序处理 $Q$ 个如下形式的查询。
查询分为以下 $2$ 种类型之一。

• 类型 1：以 1 k l r 的形式给出。将 $T_k$ 替换成 $T_k$ 与 $S$ 的第 $l$ 个字符到第 $r$ 个字符组成的子字符串的连接字符串。
• 类型 2：以 2 x y 的形式给出。若 $T_x$ 的字典序大于 $T_y$，则输出 >；若小于则输出 <；若相等则输出 =。

输入按以下格式从标准输入中给出。

$N\ Q$ $S$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

每个查询为以下形式之一：

$1\ k\ l\ r$

$2\ x\ y$

对于类型 $2$ 的查询，假设有 $q$ 次，请输出 $q$ 行。
第 $j$ 行输出对第 $j$ 个类型 $2$ 查询的答案。

样例解释 1

• 第 $1$ 个查询：将 $T_1$ 替换为 $T_1$ 与 keio 的连接字符串。此时 $T_1$ 变为 keio。
• 第 $2$ 个查询：将 $T_2$ 替换为 $T_2$ 与 procon 的连接字符串。此时 $T_2$ 变为 procon。
• 第 $3$ 个查询：比较 $T_1$ 与 $T_2$。$T_1 = $ keio，$T_2 = $ procon，按字典序比较，$T_1$ 更小，应输出 <。
• 第 $4$ 个查询：将 $T_3$ 替换为 $T_3$ 与 keioprocon 的连接字符串。此时 $T_3$ 变为 keioprocon。
• 第 $5$ 个查询：将 $T_1$ 替换为 $T_1$ 与 procon 的连接字符串。此时 $T_1$ 变为 keioprocon。
• 第 $6$ 个查询：比较 $T_1$ 与 $T_3$。$T_1 = $ keioprocon，$T_3 = $ keioprocon，按字典序相等，应输出 =。
• 第 $7$ 个查询：比较 $T_1$ 与 $T_4$。$T_1 = $ keioprocon，$T_4$ 为空字符串，按字典序 $T_4$ 更小，应输出 >。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $S$ 为仅包含小写英文字母的长度为 $N$ 的字符串
• $1 \leq k \leq 2 \times 10^5$
• $1 \leq l \leq r \leq N$
• $1 \leq x, y \leq 2 \times 10^5$
• $x \neq y$
• $N, Q, k, l, r, x, y$ 均为整数

由 ChatGPT 5 翻译