小L经常被小H怒斥：“滚！”于是小L滚了一圈，想到了一道题。
小H曾经给过小L一个长度为n的序列a_{1...n}。这给了小L灵感，于是小L自己再写出了一个长度为n的序列w_{1...n}。
小L假设小H会问他m个问题，每一个问题是这样的：小H给出三个整数l, r, k，并设f(x)表示x在a序列的区间[l, r]内的出现次数，对于所有满足f(x) > 0且存在y使得0 < f(y) < f(x) ≤ f(y) + k的x，求出w_{f(x)}的最大值。若不存在，请回答-1。
1. 第一行，两个正整数n, m。
2. 第二行，n个正整数a_1, a_2, ..., a_n。
3. 第三行，n个非负整数w_1, w_2, ..., w_n。
4. 以下m行，每行三个正整数l, r, k。
m行，每行一个整数，表示每个问题的答案。
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
2 -1 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
4 5 5
样例解释 #1
- 对于第一个问题，当x=1时存在y=2满足条件，且w_{f(x)}取最大值2。
- 对于第二个问题，不存在满足条件的x。
- 对于第三个问题，当x=3时存在y=1满足条件，且w_{f(x)}取最大值2。
样例解释 #2
- 对于第一个问题，当x=3时存在y=2满足条件，且w_{f(x)}取最大值4。
- 对于第二个问题，当x=3时存在y=2,4满足条件，且w_{f(x)}取最大值5。
- 对于第三个问题，当x=3时存在y=2满足条件，且w_{f(x)}取最大值5。
数据范围
- 对于20%的数据，n, m ≤ 10^3；
- 对于另外20%的数据，k ≤ 100；
- 对于100%的数据，1 ≤ n, m, a_i ≤ 2 \times 10^5，1 ≤ k ≤ n，0 ≤ w_i ≤ 10^9，1 ≤ l ≤ r ≤ n。
| Time Limit | 2 seconds |
| Memory Limit | 128 MB |