시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 32 MB86292734.177%

문제

For a long long time you have been a big fan of Bytelotto. For around the same time, the members of your family have been telling you that all such games are a waste of money. You are sure that it is because of their lack of skill! You have a brilliant plan and everyone will see you winning the game soon.

There are many types of games. You are interested in one of them: Bitlotto. The choice was simple, as it is the easiest offered type of game: on each day exactly one number is drawn at random. You took notes the results of draws in n consecutive days and obtained a sequence a1, a2, . . . , an. You are sure that there is some pattern in this sequence, especially in intervals of l consecutive days. Your family still does not believe you, so the only way to convince them is to use solid math.

There are n−l+1 intervals of days of length l. The i-th interval starts at position i, so it contains elements ai, ai+1, . . . , ai+l−1. The distance between two intervals is the number of mismatches on their corresponding positions. In other words, for the x-th and the y-th interval it is the number of positions i (0 ≤ i < l) such that ax+i and ay+i are different. Finally, we define two intervals to be k-similar if their distance is at most k.

There is a fixed sequence and an integer l. You are given q queries. In every query, you are given an integer kj and for each of the n − l + 1 intervals you must find the number of intervals of the same length that are kj -similar to this interval (not counting this interval itself).

입력

The first line of the standard input contains two space-separated integers n and l (1 ≤ l ≤ n ≤ 10 000), the number of days and the length of the analysed intervals. The second line contains n space-separated integers a1, a2, . . . , an (1 ≤ ai ≤ 109), where ai is the number that was drawn on the i-th day.

The third line contains an integer q (1 ≤ q ≤ 100), the number of queries. Each of the next q lines contains an integer kj (0 ≤ kj ≤ l), the similarity parameter for the j-th query.

출력

Print q lines. The j-th line should contain n − l + 1 space-separated integers that are the answer to the j-th query. The i-th number in a line should be the number of other intervals that are kj-similar to the i-th interval.

서브태스크

번호배점제한
125

n ≤ 300

220

n ≤ 2000

320

q = 1, k1 = 0

415

q = 1

520

No additional constraints

예제 입력 1

6 2
1 2 1 3 2 1
2
1
2

예제 출력 1

2 1 1 1 1
4 4 4 4 4

In the example above there are five intervals of length 2:

  • the first interval contains the numbers 1 2
  • the second contains 2 1
  • the third contains 1 3
  • the fourth contains 3 2
  • the fifth contains 2 1

There are two queries.

The first query has k = 1. The first and the third interval — 1 2 and 1 3 — differ only on the second position, so the distance between them is 1. Similarly, the first and fourth interval — 1 2 and 3 2 — differ only on the first position, so the distance is 1. These are the only two intervals that are 1-similar to the first interval, so the first printed number is 2.

In the second query we are given k = 2. All pairs of intervals are 2-similar.

채점 및 기타 정보

  • 예제는 채점하지 않는다.