102582: [AtCoder]ABC258 C - Rotation

Problem Statement

You are given positive integers $N$ and $Q$, and a string $S$ of length $N$ consisting of lowercase English letters.

Process $Q$ queries. Each query is of one of the following two types.

• 1 x: Perform the following $x$ times in a row: delete the last character of $S$ and append it to the beginning.
• 2 x: Print the $x$-th character of $S$.

Constraints

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le x \le N$
• $|S|=N$
• $S$ consists of lowercase English letters.
• At least one query in the format 2 x.
• $N$, $Q$, $x$ are all integers.

Input

Input is given from Standard Input in the following format:

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

Each query is in the following format, where $t$ is $1$ or $2$:

$t$ $x$

Output

For each query in the format 2 x, print the answer in a single line.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the $1$-st query, $S$ is abc, so the $2$-nd character b should be printed. In the $2$-nd query, $S$ is changed from abc to cab. In the $3$-rd query, $S$ is cab, so the $2$-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

问题描述

给你正整数 $N$ 和 $Q$，以及一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。

处理 $Q$ 个查询。每个查询为以下两种类型之一。

• 1 x：连续执行 $x$ 次：删除 $S$ 的最后一个字符并将其添加到开头。
• 2 x：输出 $S$ 的第 $x$ 个字符。

约束条件

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le x \le N$
• $|S|=N$
• $S$ 由小写英文字母组成。
• 至少有一个格式为 2 x 的查询。
• $N$，$Q$，$x$ 都是整数。

输入

输入从标准输入中给出，如下所示：

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

每个查询的格式如下，其中 $t$ 是 $1$ 或 $2$：

$t$ $x$

输出

对于每个格式为 2 x 的查询，输出答案在同一行中。

样例输入 1

3 3
abc
2 2
1 1
2 2

样例输出 1

b
a

在第 $1$ 个查询中，$S$ 是 abc，因此应输出第 $2$ 个字符 b。 在第 $2$ 个查询中，$S$ 从 abc 变为 cab。 在第 $3$ 个查询中，$S$ 是 cab，因此应输出第 $2$ 个字符 a。

样例输入 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

样例输出 2

c
u
c
u