Bessie đang luyện các màn ảo thuật với bài. Cô đã thành thạo phép xáo bài Bessie: một phép xáo trên \(M\) lá bài (\(2 \le M \le 100\,000\)), sắp xếp lại sao cho lá bài thứ \(i\) tính từ trên xuống chuyển đến vị trí thứ \(P[i]\) tính từ trên xuống.

Giờ đây, Bessie đang luyện xáo những bộ bài lớn hơn. Cô có một bộ gồm \(N\) lá bài (\(M \le N \le 1\,000\,000\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\). Cô xáo bộ bài này bằng cách lấy \(M\) lá đầu tiên, thực hiện phép xáo Bessie trên chúng, rồi đặt các lá đã xáo trở lại trên cùng bộ bài. Sau đó, cô lấy lá trên cùng ra và đặt úp xuống. Cô lặp lại quá trình này, lần lượt đặt các lá trên cùng chồng lên nhau, cho đến khi không còn lá nào. Khi còn ít hơn \(M\) lá, Bessie không thực hiện phép xáo Bessie nữa nhưng vẫn tiếp tục đặt lá trên cùng lên trên các lá còn lại.

Bessie biết rằng ban đầu bộ bài được sắp theo thứ tự, với lá \(1\) ở trên cùng, tiếp theo là lá \(2\), và lá \(N\) ở dưới cùng. Cho mô tả của phép xáo Bessie, hãy giúp Bessie xác định những lá bài nằm tại \(Q\) vị trí được chỉ định khác nhau (\(1 \le Q \le N\), \(Q \le 5\,000\)) trong bộ bài cuối cùng.

Dữ liệu vào

• Dòng đầu tiên chứa ba số \(N\), \(M\) và \(Q\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(P[i]\), là vị trí tính từ trên xuống của lá bài thứ \(i\) sau phép xáo Bessie.
• \(Q\) dòng cuối, dòng thứ \(i\) chứa một số nguyên \(q_i\). Bạn cần xác định nhãn của lá bài nằm ở vị trí \(q_i\) tính từ trên xuống.

Ràng buộc

• \(2 \le M \le 100\,000\).
• \(M \le N \le 1\,000\,000\,000\).
• \(1 \le Q \le N\) và \(Q \le 5\,000\); các vị trí được truy vấn đôi một khác nhau.
• \(1 \le P[i] \le M\).
• \(1 \le q_i \le N\).

Phân nhóm

• \(50\%\) số bộ kiểm thử có \(N \le 100\,000\).

Dữ liệu ra

Với mỗi truy vấn \(i\), in ra trên dòng thứ \(i\) một số nguyên là nhãn của lá bài tại vị trí \(q_i\) tính từ trên xuống.

Ví dụ

5 3 5
3
1
2
1
2
3
4
5

4
5
3
1
2

Nguồn

USACO 2013 December Contest, Gold — Problem 3: The Bessie Shuffle (gold)

Tác giả: Mark Gordon, 2013.