众所周知，二分只有两种， 和 。 可以在有序区间 内找到第一个大于等于 的元素的指针位置。 可以在有序区间 内找到第一个大于 的元素的指针位置。 于是我们可以推理出四个规则： 1. 最小的 使得 的指针为 。 2. 最小的 使得 的指针为 。 3. 最大的 使得 的指针为 。 4. 最大的 使得 的指针为 。 有时，得到的指针位置并不合法。 如果我们强行去访问指针所指向的内存，可能会触发 段错误 。 给定一个长度为 的有序数组 ，下标从 开始。 以及 次询问，每次询问给出操作数 ，一个左闭右开区间 和一个数字 。 只可能是 中的一种，需要你按照上述规则去找对应的 。 如果找不到，请输出 。

输入描述:

第一行有两个整数 和 。第二行有 个整数 ，保证有 。随后 行，每行有四个整数 ， 和 。

输出描述:

输出 行，每行一个整数，代表对应的 值。如果找不到，输出 。