Công ty do Bờm làm Giám đốc có mua một con Robot được điều khiển bằng một đoạn băng từ. Băng từ gồm ~n~ (~1 \le n \le 10^5~) ô liên tiếp được đánh số ~1, 2, \ldots, n~ từ trái qua phải. Ô thứ ~i~ của băng từ chứa số nguyên ~a_i~ có giá trị nằm trong đoạn ~[1, n]~. Công việc của Robot như sau:

• Bước 1: Robot bắt đầu làm việc ở ô thứ ~i~ của băng từ;
• Bước 2: tại vị trí Robot đang đứng nó đọc số nguyên dương ~a_i~ ở ô này và tự động di chuyển đến ô thứ ~a_i~ của băng từ (được tính là một lần di chuyển);
• Bước 3: sau khi di chuyển đến ô thứ ~a_i~, Robot tiếp tục thực hiện lại Bước 2.

Để phục vụ công việc của công ty, Bờm muốn biết khi Robot bắt đầu ở ô thứ ~i~ thì sau ~k~ lần di chuyển Robot đứng tại ô nào của băng từ?

Yêu cầu: cho giá trị các ô của băng từ. Bờm có ~q~ câu hỏi, mỗi câu hỏi gồm hai số nguyên dương ~i, k~ tương ứng là vị trí ô bắt đầu làm việc và số lần di chuyển của Robot. Hãy giúp Bờm trả lời ~q~ câu hỏi đã cho.

Dữ liệu

• Dòng đầu tiên gồm 2 số nguyên dương ~n~ và ~q~;
• Dòng thứ 2 gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ là giá trị các ô của băng từ;
• ~q~ dòng tiếp, mỗi dòng gồm 2 số ~i~ và ~k~ là vị trí ô bắt đầu làm việc và số lần di chuyển của Robot.

Kết quả

Gồm ~q~ dòng, mỗi dòng chứa kết quả tương ứng với mỗi câu hỏi.

Ví dụ

Ví dụ 1

MOVE.INP

5 2
2 1 3 5 4
1 3
3 10

MOVE.OUT

2
3

Giải thích:

• Ở câu hỏi thứ nhất, thứ tự di chuyển là: 1 → 2 → 1 → 2;
• Ở câu hỏi thứ hai, thứ tự di chuyển là: 3 → 3 → 3 → ... → 3.

Ví dụ 2

MOVE.INP

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

MOVE.OUT

2
3
3

Giải thích:

• Ở câu hỏi thứ nhất, thứ tự di chuyển là: 2 → 3 → 4 → 2;
• Ở câu hỏi thứ hai, thứ tự di chuyển là: 1 → 2 → 3 → 4 → 2 → 3;
• Ở câu hỏi thứ ba, thứ tự di chuyển là: 4 → 2 → 3.

Giới hạn

• Subtask 1 (20% số test): ~1 \le n, k, q \le 5000~;
• Subtask 2 (30% số test): ~1 \le n, q \le 10^4~; ~1 \le k \le 10^6~;
• Subtask 3 (40% số test): ~1 \le n, q \le 10^5~; ~1 \le k \le 10^9~;
• Subtask 4 (10% số test): ~1 \le n, q \le 10^5~; ~1 \le k \le 10^{18}~.