题目描述

噜噜有一个长度为 $n$ 的序列 $a$，第 $i$ 个位置初始为 $a_i$。
接下来他会对序列进行 $q$ 次操作，每次操作为如下四种之一：

• 1 l r：将子区间 $[l,r]$ 内的元素升序排序；
• 2 l r：将子区间 $[l,r]$ 内的元素降序排序；
• 3 l r：将子区间 $[l,r]$ 内的元素整体翻转；
• 4 l r k：依次对 $i=l,l+1,\dots,r$ 执行 swap(a[i], a[i+k])（保证 $r+k\le n, k\ge1$）。

请你在这 $q$ 次操作全部执行完之后，回答序列最小值所在的位置。
保证序列中数值两两不同，答案唯一。

输入格式

本题有多组数据。
第一行一个正整数 $T$ 表示数据组数。对每组数据：

• 第一行两个正整数 $n, q$；
• 第二行 $n$ 个正整数 $a_1,\dots,a_n$；
• 接下来 $q$ 行，每行描述一次操作，格式同上，第一项为操作类型 $t$。

输出格式

对每组数据输出一行，一个正整数，表示最终最小值的位置。

样例输入

1
6 5
1 2 3 4 5 6
2 1 4
1 2 3
3 2 4
4 1 3 2
4 1 2 3

样例输出

1

样例解释

初始 $a=(1,2,3,4,5,6)$。
操作依次得到：

1. 2 1 4 → $(4,3,2,1,5,6)$
2. 1 2 3 → $(4,2,3,1,5,6)$
3. 3 2 4 → $(4,1,3,2,5,6)$
4. 4 1 3 2 → $(3,2,5,1,4,6)$
5. 4 1 2 3 → $(1,4,5,3,2,6)$

最终最小值为 $1$，位置为 $1$。

数据范围

• 对于 $100$ 的数据：$1\le T\le10, 1\le n,q\le 2\times10^5, 1\le a_i\le 10^9$；$a_i$ 两两不同。
• 测试点划分：