题目描述

猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题：

输入格式

第一行两个非负整数 n, q。

输出格式

见样例

样例

样例 1

输入 # 1

5 5

3 2 1 4 3

2 1 5

1 2 4 2

2 1 5

1 2 5 1

2 1 5

输出 # 1

3

5

1