描述

给出N及一列N个数\(A_1\),\(A_2\),...,\(A_N\)
M次询问
每次询问给出两个参数f,p
f=1表示询问p后大于\(A_p\)的第一个数(最靠前)的位置
f=2表示询问p前大于\(A_p\)的第一个数(最靠后)的位置
f=3表示询问p前小于\(A_p\)的第一个数(最靠后)的位置
f=4表示询问p后小于\(A_p\)的第一个数(最靠前)的位置

输入

第一行两个正整数N,M
第二行N个整数
接下来M行，每行两个数f,p

输出

M行，每行一个整数为所求位置，该位置不存在则输出-1

样例

输入

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

输出

3
1
-1
1

范围

50% N<=3000 M<=3000
70% N<=50000 M<=50000
90% N<=\(10^6\) M<=500000
100% N<=\(7\ast 10^6\) M<=\(10^6\)

限制

1s
128M