题目描述

mzx去爬山了！现在有一排山，编号从1到n。

在m天之内，mzx每天都去爬山。每天，mzx都会选择一座山作为起点，向左或向右爬到第k个比起点高或低的山峰。

mzx想知道他每天会爬到哪座山。

输入格式

第一行两个整数n,m；

第二行为用空格隔开的n个数，代表编号为1到n的山峰的高度。

从第三行到第m+2行，每行四个数a,b,x,k代表mzx这一天的爬山计划。

x是作为起点的山峰的编号，a=0代表mzx会向左出发，a=1代表mzx会向右出发；b=0代表mzx要爬到第k个比起点低的山峰，b=1代表mzx要爬到第k个比起点高的山峰。

输出格式

输出mzx在第1到第m天爬到的那座山的编号，每个编号占一行。

如果不存在符合要求的山峰，输出 “-1”。

样例数据

input

5 3

4 1 3 10 2

0 0 2 1

1 1 2 1

0 1 5 2

output

-1

3

3

数据规模与约定

$1 \leq n,m \leq 5000$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$