题目描述

小 $\red{L }$经常被小 $\red{H }$怒斥：「滚！」

于是小 $\red{L }$滚了一圈，想到了一道题。

小 $\red{H }$曾经给过小 $\red{L }$一个长度为$\red{n}$的序列$\red{a_1..n}$。

这给了小 $\red{L }$灵感，于是小 $\red{L }$自己再写出了一个长度为$\red{n}$的序列$\red{w_1...n}$。

小 $\red{L }$假设小 $\red{H }$会问他$\red{m}$个问题，每一个问题是这样的：

小 $\red{H }$给出三个整数$\red{l,r,k，}$并设$\red{f(x)}$表示$\red{x}$在$\red{a}$序列的区间$\red{[l,r]}$内的出现次数，对于所有满足$\red{f(x)>0}$ 且存在$\red{y}$使得$\red{0<f(y)<f(x)<=f(y)+k}$的$\red{x，}$求出$\red{w_{f(x)}}$的最大值。

若不存在，请回答$\red{-1}$。

小 $\red{L }$希望你帮他回答他设想的这$\red{m}$个问题。

输入格式

第一行，两个正整数 $\red{n, m}$。（$\red{n,m≤}$$\red{2e5）}$

第二行，$\red{n }$个正整数 $\red{a_1, a_2, ..., a_n}$。

第三行，$\red{n }$个非负整数 $\red{w_1, w_2, ..., w_n}$。

以下 $\red{m }$行，每行三个正整数 $\red{l, r, k}$。

输出格式

$\red{m }$行，每行一个整数，表示每个问题的答案。

样例

输入样例1

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

输出样例1

2
-1
2

输入样例2

10 3
1 2 3 3 2 3 3 2 4 4
1 1 4 5 1 4 1 9 1 9
2 6 1
3 9 3
1 10 1

输出样例2

4
5
5

提示

样例 #$\red{1：}$

对于第一个问题，当$\red{x=1}$时存在$\red{y=2}$满足条件，且$\red{w_{f(x)}}$取最大值$\red{2}$。

对于第二个问题，不存在满足条件的$\red{x}$。

对于第三个问题，当$\red{x=3}$时存在$\red{y=1}$满足条件，且$\red{w_(f(x))}$取最大值$\red{2}$。

样例 #$\red{2：}$

对于第一个问题，当$\red{x=3}$时存在$\red{y=2}$满足条件，且$\red{w_{f_(x)}}$取最大值$\red{4}$。

对于第二个问题，当$\red{x=3}$时存在$\red{y=2,4}$满足条件，且$\red{w_{f_(x)}}$取最大值$\red{5}$。

对于第三个问题，当$\red{x=3}$时存在$\red{y=2}$满足条件，且$\red{w_{f_(x)}}$取最大值$\red{5}$。