Xáo Bài Bessie

Có một bộ bài $N$ lá được đánh số $1$ đến $N$ theo thứ tự từ trên xuống dưới. Cho một hoán vị $P$ gồm $M$ phần tử mô tả thao tác xáo bài: lá bài ở vị trí $i$ trong nhóm $M$ lá trên cùng sẽ chuyển sang vị trí $P[i]$.

Thực hiện thao tác sau lặp đi lặp lại cho đến khi bộ bài còn ít hơn $M$ lá:

1. Xáo $M$ lá trên cùng theo hoán vị $P$.
2. Lấy lá bài trên cùng ra và úp xuống (xây một chồng bài mặt-xuống).

Sau đó, các lá bài còn lại trong bộ bài được úp xuống từng lá một (từ trên xuống).

Chồng bài mặt-xuống sau khi hoàn thành: vị trí $1$ là lá trên cùng (lá úp xuống cuối cùng), vị trí $N$ là lá dưới cùng (lá úp xuống đầu tiên).

Cho $Q$ truy vấn, mỗi truy vấn hỏi lá bài ở vị trí $q_i$ trong chồng bài cuối cùng.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $M$, $Q$.
• $M$ dòng tiếp theo: Số nguyên $P[i]$ — mỗi dòng một giá trị.
• $Q$ dòng tiếp theo: Số nguyên $q_i$ — vị trí truy vấn.

Dữ liệu ra

• $Q$ dòng, mỗi dòng là nhãn của lá bài tại vị trí $q_i$ trong chồng bài cuối cùng.

Ràng buộc

• $2\le M\le 100000$
• $M\le N\le 100000$
• $1\le Q\le 5000$
• $1\le P[i]\le M$ (hoán vị hợp lệ)
• $1\le q_i\le N$

Ví dụ

Ghi chú

• Số lần xáo bài là $R=N-M+1$, sau đó còn lại $M-1$ lá được úp xuống.
• Vị trí $1$ đến $M-1$ tương ứng với $M-1$ lá cuối úp xuống (theo thứ tự ngược).
• Vị trí $M$ đến $N$ là các lá bị lấy ra trong các lần xáo (theo thứ tự từ gần nhất đến xa nhất).