问题描述

给定一个长度为 $n$，且非严格递增的序列 $A$。

再给定 $q$ 组查询，每组查询为：

1 l r x：输出 $A_{l\sim r}$ 中等于 $x$ 最左边的数的下标，若不存在输出 -1。

2 l r x：输出 $A_{l\sim r}$ 中等于 $x$ 最右边的数的下标，若不存在输出 -1。

3 l r x：输出 $A_{l\sim r}$ 中大于等于 $x$ 的第一个数的下标，若不存在输出 -1。

4 l r x：输出 $A_{l\sim r}$ 中大于 $x$ 的第一个数的下标，若不存在输出 -1。

输入格式

第一行输入两个正整数 $n,q$。$(1\le n,q\le 10^5)$

第二行输出 $n$ 个整数 $A_i$。$(1\le A_i\le 10^5,1\le i\le 10^5 ,1\le q\le 10^5)$

接下来 $q$ 行输入，表示查询，具体为：

1 l r x：输出 $A_{l\sim r}$ 中等于 $x$ 最左边的数的下标，若不存在输出 -1。

2 l r x：输出 $A_{l\sim r}$ 中等于 $x$ 最右边的数的下标，若不存在输出 -1。

3 l r x：输出 $A_{l\sim r}$ 中大于等于 $x$ 的第一个数的下标，若不存在输出 -1。

4 l r x：输出 $A_{l\sim r}$ 中大于 $x$ 的第一个数的下标，若不存在输出 -1。

$1\le x\le 10^5,1\le l\le r\le n$。

输出格式

对于每组查询，输出一个整数，为按照题目要求查询的结果。

样例输入

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

样例输出

2
4
2
-1
-1
5