Cho mảng ~a~ gồm ~a_1,a_2,...,a_n~ là một hoán vị của ~1,2,...,n~ và một số nguyên ~x~.

Ta chọn ~b_i~ là vị trí của giá trị trong mảng ~a~ nhỏ hơn ~a_i~ và có vị trí gần ~i~ nhất. Nếu có ~2~ giá trị cùng nhỏ hơn ~a_i~ và khoảng cách của chúng tới ~i~ là bằng nhau thì chọn vị trí của giá trị lớn hơn trong hai giá trị đó.

Mỗi giây, với mỗi ~i~ từ ~1~ tới ~n~, ta thay ~a_i~ bằng ~a_{b_i}~. Nếu vị trí ~i~ không tồn tại giá trị ~b_i~ thì ~a_i=0~. (Giá trị ~b_i~ không thay đổi qua các giây)

Cho ~q~ truy vấn. Với mỗi truy vấn cho một số nguyên dương ~k~, bạn cần trả lời sau ít nhất bao nhiêu giây thì có ít nhất ~k~ phần tử ~a_i~ trong mảng sao cho ~a_i \le x~.

Ví dụ: ~a = [4, 2, 3, 7, 8, 6, 5, 1]~, ta sẽ có ~b = [2, 8, 2, 3, 4, 7, 8, \emptyset]~ (~\emptyset~ nghĩa là không tồn tại giá trị).

• Sau giây thứ nhất ~a = [2, 1, 2, 3, 7, 5, 1, 0]~.
• Sau giây thứ hai ~a = [1, 0, 1, 2, 3, 1, 0, 0]~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, q, x~ ~(1\le n, q \le5 \times 10^5, 0 \le x \le n)~ - lần lượt là độ dài của mảng ~a~, số truy vấn và hằng số nguyên bất kì.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1\le a_i \le n)~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ là một số nguyên dương ~k~ ~(k \le n)~ thể hiện truy vấn thứ ~i~.

Output

In kết quả trên ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• ~20\%~ số test có ~n \le 3000~.
• ~30\%~ số test có ~x = 0~.
• ~30\%~ số test có ~q \le 3~.
• Các test còn lại không có điều kiện gì thêm.

Sample Input 1

8 8 2
4 2 3 7 8 6 5 1
1
2
3
4
5
6
7
8

Sample Output 1

0
0
1
1
1
2
2
3