Misaka Mikoto's Sequence Intervals Query

Given a sequence of n integers, [a1, a2, ..., an], and m intervals [l1, r1], [l2, r2], ..., [lm, rm], you are to answer q queries.

Each query provides three integers L, R, k. For each query, consider the intervals with indices from L to R (1-indexed). For every such interval [li, ri], compute the sum:

$$S_i = \sum_{j=l_i}^{r_i} [a_j = k]$$

where \( [a_j = k] \) is the indicator function that equals 1 if \(a_j = k\) and 0 otherwise. Your task is to output the maximum value among \( S_i \) for \( i \) from L to R:

$$\max_{i=L}^{R} S_i$$

inputFormat

The input is given in the following format:

 n m
 a1 a2 ... an
 l1 r1
 l2 r2
 ...
 lm rm
 q
 L1 R1 k1
 L2 R2 k2
 ...
 Lq Rq kq

All indices are 1-indexed.

outputFormat

For each query, output a single integer on a new line representing the maximum count of k in any interval between indices L and R.

sample

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

2
2
0