题面下载

样例下载

时间限制： 2.0 秒

空间限制： 512 MB

题目背景

在探索“曙梦星海”的深处时，通讯雷达捕获到了一段来自未知古老文明的遗迹信号。首席解密官小研正在对这段由大写字母组成的加密波段进行清洗与重组。

题目描述

给定一个长度为 $n$ 的字符串 $s$（代表初始信号），只包含大写字母，字符坐标分别按 $1,\cdots,n$ 排列。小研会依次进行 $m$ 次操作对信号进行解析，每种操作为以下三种之一：

1. $1\ l\ r\ c$：在信号坐标频段的 $[l,r]$ 范围内，扫描字符 $c$ 最早出现的位置坐标，若不存在则返回 $-1$。
2. $2\ l\ r\ c$：进行信号覆写，将 $[l,r]$ 范围内的所有字符全部修改为 $c$。
3. $3\ l\ r$：进行信号重组，将 $[l,r]$ 范围内的所有字符按照字母表顺序重新排序。

输入格式

从标准输入读入数据。

第一行输入两个整数 $n,m$。

第二行输入一个长度为 $n$ 的字符串 $s$。

接下来 $m$ 行，每行描述一次小研的具体操作。

输出格式

输出到标准输出。

对于每一次类型为 $1$ 的查询操作，输出一行一个整数，表示查询的位置结果。

10 5
ABCDABCDCD
1 1 3 A
3 1 5
1 1 3 A
2 1 2 B
1 2 3 B

1
1
2

样例 1 解释

子任务

对于所有数据：

• $n,m\le 10^5$；
• $1\le l\le r\le n$；
• 出现的字符全部为大写字母（[A-Z]）

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。