Phát ordered a huge cake decorated with candles of different colors for his little sister's birthday! There are ~n~ candles on the cake, with colors ~c_1, c_2, \ldots, c_n~ from left to right.

His sister likes it so much! After blowing the candles, she wants to cut the first piece for her beloved brother. To cut a piece of the cake, she needs to select two indices ~l~ and ~r~ (~1 \le l \le r \le n~), so that the piece cut out will include candles with colors ~c_l, c_{l + 1}, \ldots, c_r~.

She loves her brother so much that she wants the piece of the cake cut
out to be *sparkling*. A piece of the cake is called *sparkling* if, for
each candle color that appears on the cake, there exist exactly ~k~
candles with that color, where ~k~ is the highest number that she knows
how to count up to with her fingers.

For example, with ~k = 2~, the piece of the cake with candles
~[1, 4, 1, 2, 2, 4]~ is *sparkling*: there are two candles of color ~1~,
two candles of color ~2~, and two candles of color ~4~. On the other
hand, the cake piece with candles ~[1, 1, 2, 3]~ is not *sparkling*, as
there is only one candle of color ~2~, as well as only one candle of
color ~3~.

Currently, his sister can think of ~q~ ways to cut the cake. For the
~i~-th way, she wants to cut the piece with candles from indices ~l_i~
to ~r_i~. Help the little sister, for each way of cutting, to check if
the resulting cake piece is *sparkling*. If the piece is not
*sparkling*, point out a color that appears on the cake piece, but the
number of candles of that color is not exactly ~k~, so she can
re-decorate the cake! If there is more than one such color, point out
any.

#### Input

The first line contains two integers ~n~ and ~k~ (~1 \le n \le 10^6~, ~1 \le k \le 5~), denoting the number of candles on the cake, and the number that Phát's sister can count up to.

The next line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le n~, for all ~1 \le i \le n~), denoting the colors of the candles on the cake, from left to right.

The next line contains an integer ~q~ (~1 \le q \le 10^6~), the number of ways to cut the cake that the little sister thinks of.

The ~i~-th line out of the next ~q~ lines contains two integers ~l_i~ and ~r_i~ (~1 \le l_i \le r_i \le n~) denoting a way to cut the cake, such that the cake contains candles with indices ~l_i~ to ~r_i~.

#### Output

Output ~q~ lines. For the ~i~-th line, output ~0~ if the ~i~-th way of
cutting the cake is *sparkling*. Otherwise, output a color such that the
number of candles with that color on the piece of cake is more than ~0~
but not ~k~. If there are multiple such colors, output any.

#### Scoring

Subtask 1 (~80~ points): ~n \le 1000~ and ~q \le 1000~.

Subtask 2 (~180~ points): No additional constraints

The total score for this problem is ~260~.

#### Sample Input 1

```
9 2
1 3 1 3 2 2 1 1 2
9
1 6
2 7
5 8
6 9
7 8
1 4
3 6
4 8
2 8
```

#### Sample Output 1

```
0
0
0
0
0
0
1
3
1
```

#### Notes

In the first example, Phát's little sister can count up to ~k = 2~.

For the first way, ~l = 1~, ~r = 6~. The sequence of candles is
~[1, 3, 1, 3, 2, 2]~. This cake piece is *sparkling*, as there are two
candles with color ~1~, two candles with color ~2~ and two candles with
color ~3~.

For the 6-th way, ~l = 1~, ~r = 4~. The sequence of candles is
~[1, 3, 1, 3]~. This piece is also *sparkling*, as there are two candles
with color ~1~, two candles with color ~3~, and no candles of other
colors.

For the 7-th way, ~l = 3~, ~r = 6~. The sequence of candles is
~[1, 3, 2, 2]~. This piece is not *sparkling* as there is only one
candle of color ~1~ and one candle of color ~3~. Therefore outputting
either ~1~ or ~3~ is a valid answer.

For the last way, ~l = 2~, ~r = 8~. The sequence of candles is
~[3, 1, 3, 2, 2, 1, 1]~. This piece is not *sparkling*, as there are
three candles of color ~1~.

## Comments

This comment is hidden due to too much negative feedback. Show it anyway.