To read the problem statement in English, choose the language using the flag on the navigation bar.

Nhân ngày sinh nhật em gái của mình, Phát đã đặt mua một chiếc bánh lớn được trang trí bởi một dãy nến với đủ loại màu sắc. Trên bánh có ~n~ cây nến có màu sắc lần lượt là ~c_1, c_2, \ldots, c_n~ từ trái qua phải.

Em gái của Phát thích lắm! Sau khi thổi nến xong, em gái ngoan muốn cắt miếng bánh đầu tiên mời anh trai của mình. Để cắt một miếng bánh, em gái cần chọn hai chỉ số ~l~ và ~r~ (~1 \le l \le r \le n~), và miếng bánh được cắt ra sẽ bao gồm các cây nến với màu sắc ~c_l, c_{l + 1}, \ldots, c_r~.

Rất quý mến anh trai Phát, em gái muốn miếng bánh được cắt ra phải là miếng bánh rực rỡ. Miếng bánh được gọi là rực rỡ nếu như với mỗi màu sắc của từng cây nến trên miếng bánh, tồn tại đúng ~k~ cây nến với màu sắc đó trên miếng bánh, với ~k~ là số lớn nhất mà em gái đã đếm được trên đầu ngón tay.

Ví dụ, với ~k = 2~, miếng bánh từ dãy nến ~[1, 4, 1, 2, 2, 4]~ là một miếng bánh rực rỡ: trên miếng bánh này tồn tại hai cây nến có màu ~1~, hai cây nến có màu ~2~ và hai cây nến có màu ~4~. Ngược lại, chiếc bánh ~[1, 1, 2, 3]~ không rực rỡ, bởi vì nhưng chỉ có một cây nến có màu ~2~ và một cây nến có màu ~3~.

Hiện tại em gái đang có ~q~ cách cắt bánh. Với mỗi cách thứ ~i~, em gái muốn cắt bánh từ vị trí ~l_i~ đến ~r_i~. Hãy giúp em gái kiểm tra xem, với từng cách cắt, miếng bánh được cắt theo cách đó có rực rỡ không. Nếu như miếng bánh không rực rỡ, hãy giúp em gái chỉ ra một màu sắc với số lượng cây nến trên miếng bánh dương nhưng khác ~k~, để em gái có thể trang trí lại miếng bánh cho rực rỡ!. Nếu có nhiều màu như vậy, hãy in ra màu bất kì.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^6~, ~1 \le k \le 5~), lần lượt là số lượng cây nến trên chiếc bánh và số lớn nhất hiện tại mà em gái của Phát đã đếm được.

Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le n~, với mọi ~1 \le i \le n~) là màu sắc của các cây nến trên chiếc bánh theo thứ tự từ trái qua phải.

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 10^6~) là số lượng cách cắt bánh mà em gái có.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~) thể hiện một cách cắt bánh bao gồm các cây nến từ vị trí ~l_i~ đến ~r_i~ trên chiếc bánh.

Output

Hãy in ra ~q~ dòng. Trên dòng thứ ~i~ hãy in ra ~0~ nếu như miếng bánh với cách cắt thứ ~i~ là miếng bánh rực rỡ. Ngược lại, in ra chỉ số của màu với số lượng cây nến trên miếng bánh lớn hơn ~0~ nhưng khác ~k~. Nếu có nhiều màu thỏa mãn, hãy in ra màu bất kì.

Scoring

• Subtask 1, tương ứng với ~80~ điểm, có ~n \le 1000~ và ~q \le 1000~.

• Subtask 2, tương ứng với ~180~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~260~ điểm.

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

Trong ví dụ, số lớn nhất mà em gái của Phát đã đếm được trên đầu ngón tay là ~k = 2~.

Với cách cắt đầu tiên, ~l = 1~, ~r = 6~. Các cây nến trên miếng bánh này có màu tạo thành dãy ~[1, 3, 1, 3, 2, 2]~. Đây là miếng bánh rực rỡ, vì trên miếng bánh có hai cây nến có màu ~1~, hai cây nến có màu ~2~ và hai cây nến có màu ~3~.

Với cách cắt thứ 6, ~l = 1~, ~r = 4~. Các cây nến trên miếng bánh này có dãy màu là ~[1, 3, 1, 3]~. Đây cũng là miếng bánh rực rỡ, vì trên miếng bánh có hai cây nến màu ~1~, hai cây nến màu ~3~, và không có cây nến màu khác.

Với cách cắt thứ 7, ~l = 3~, ~r = 6~. Các cây nến trên miếng bánh này có các màu lần lượt là ~[1, 3, 2, 2]~. Miếng bánh này không rực rỡ do chỉ có một cây nến màu ~1~ và một cây nến màu ~3~. Do đó ~1~ hoặc ~3~ là đáp án cho cách cắt này.

Với cách cắt cuối cùng, ~l = 2~, ~r = 8~. Các cây nến trên miếng bánh này có màu tạo biểu diễn bởi dãy ~[3, 1, 3, 2, 2, 1, 1]~. Miếng bánh này không rực rỡ, do số lượng cây nến với màu ~1~ là ba.