로또

아주 오랫동안 당신은 Bytelotto의 열렬한 팬이었다. 거의 같은 기간 동안 가족들은 그런 게임은 모두 돈 낭비라고 말해 왔다. 당신은 그것이 가족들의 실력 부족 때문이라고 확신한다! 당신에게는 훌륭한 계획이 있고, 곧 모두가 당신이 게임에서 이기는 모습을 보게 될 것이다.

게임에는 여러 종류가 있다. 당신은 그중 하나인 Bitlotto에 관심이 있다. 선택은 간단했다. 제공되는 게임 중 가장 쉬운 종류이기 때문이다. 매일 정확히 하나의 숫자가 무작위로 추첨된다. 당신은 연속한 n일 동안의 추첨 결과를 기록하여 수열 a1, a2, . . . , an을 얻었다. 당신은 이 수열에, 특히 l일 연속 구간에 어떤 규칙이 있다고 확신한다. 가족들은 여전히 당신을 믿지 않으므로, 그들을 설득할 유일한 방법은 탄탄한 수학을 사용하는 것이다.

길이 l인 구간은 n−l+1개 있다. i번째 구간은 위치 i에서 시작하므로 ai, ai+1, . . . , ai+l−1을 포함한다. 두 구간 사이의 거리는 대응하는 위치에서 일치하지 않는 개수이다. 다시 말해, x번째 구간과 y번째 구간의 거리는 ax+i와 ay+i가 다른 위치 i (0 ≤ i < l)의 개수이다. 마지막으로, 두 구간의 거리가 k 이하이면 두 구간이 k-유사하다고 정의한다.

고정된 수열과 정수 l이 있다. q개의 질의가 주어진다. 각 질의에서 정수 kj가 주어지고, n − l + 1개의 구간 각각에 대해 같은 길이의 구간 중 이 구간과 kj-유사한 구간의 개수를 구해야 한다(이 구간 자신은 세지 않는다).

표준 입력의 첫 번째 줄에는 공백으로 구분된 두 정수 n과 l (1 ≤ l ≤ n ≤ 10 000)이 주어진다. 이는 일수와 분석할 구간의 길이이다. 두 번째 줄에는 공백으로 구분된 n개의 정수 a1, a2, . . . , an (1 ≤ ai ≤ 10^9)이 주어지며, ai는 i번째 날에 추첨된 숫자이다.

세 번째 줄에는 정수 q (1 ≤ q ≤ 100)가 주어지며, 이는 질의의 개수이다. 다음 q개 줄에는 각각 정수 kj (0 ≤ kj ≤ l)가 주어지며, 이는 j번째 질의의 유사도 매개변수이다.

q개 줄을 출력한다. j번째 줄에는 j번째 질의의 답인 n − l + 1개의 정수를 공백으로 구분하여 출력한다. 줄의 i번째 숫자는 i번째 구간과 kj-유사한 다른 구간의 개수이다.