Bạn đã yêu thích trò xổ số Bytelotto từ lâu, nhưng gia đình luôn cho rằng chơi xổ số chỉ lãng phí tiền bạc. Bạn tin rằng họ nói vậy vì chưa biết cách chơi giỏi, và muốn chứng minh điều đó bằng toán học. Trong các trò xổ số, bạn chọn Bitlotto vì đây là trò đơn giản nhất: mỗi ngày có đúng một số được rút.

Bạn đã ghi lại kết quả quay số trong \(n\) ngày liên tiếp, tạo thành dãy \(a_1,a_2,\ldots,a_n\). Xét tất cả các đoạn liên tiếp có độ dài \(l\). Đoạn thứ \(i\) gồm các phần tử \(a_i,a_{i+1},\ldots,a_{i+l-1}\).

Khoảng cách giữa hai đoạn là số vị trí mà các phần tử tương ứng khác nhau. Hai đoạn được gọi là \(k\)-tương tự nếu khoảng cách giữa chúng không vượt quá \(k\).

Bạn cần trả lời \(q\) truy vấn. Với mỗi truy vấn cho một giá trị \(k_j\), hãy xác định với từng đoạn có bao nhiêu đoạn khác cùng độ dài là \(k_j\)-tương tự với nó. Không tính chính đoạn đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,l\) (\(1\le l\le n\le10000\)), lần lượt là số ngày và độ dài mỗi đoạn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(1\le a_i\le10^9\)).

Dòng thứ ba chứa số nguyên \(q\) (\(1\le q\le100\)), là số truy vấn.

Mỗi dòng trong \(q\) dòng tiếp theo chứa số nguyên \(k_j\) (\(0\le k_j\le l\)).

Dữ liệu ra

Với mỗi truy vấn, in một dòng gồm \(n-l+1\) số nguyên. Số thứ \(i\) là số đoạn khác \(k_j\)-tương tự với đoạn thứ \(i\).

Ví dụ

6 2
1 2 1 3 2 1
2
1
2

2 1 1 1 1
4 4 4 4 4

Giải thích

Có năm đoạn độ dài \(2\): \((1,2)\), \((2,1)\), \((1,3)\), \((3,2)\) và \((2,1)\). Với \(k=1\), hai đoạn đầu tiên và đoạn thứ ba khác nhau đúng một vị trí; đoạn thứ nhất và đoạn thứ tư cũng vậy. Do đó, đoạn thứ nhất có hai đoạn khác \(1\)-tương tự. Với \(k=2\), mọi cặp đoạn đều \(2\)-tương tự.

Phân nhóm

1. \(25\) điểm: \(n\le300\).
2. \(20\) điểm: \(n\le2000\).
3. \(20\) điểm: \(q=1\) và \(k_1=0\).
4. \(15\) điểm: \(q=1\).
5. \(20\) điểm: Không có ràng buộc bổ sung.