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~.