Bitlotto k-Similarity Intervals

You are given a sequence of n lottery numbers \(a_1, a_2, \ldots, a_n\) representing consecutive winning numbers in the Bitlotto game. There are a total of \(n-l+1\) contiguous intervals of length \(l\). The \(i\)-th interval is \( [a_i, a_{i+1}, \ldots, a_{i+l-1}] \).

The distance between two intervals is defined as the number of positions at which the corresponding numbers are different. Formally, the distance between the \(x\)-th and \(y\)-th intervals is given by:

\[ d(x,y)=\sum_{i=0}^{l-1} \mathbf{1}(a_{x+i}\neq a_{y+i}) \]

Two intervals are said to be k-similar if their distance is at most \(k\). You are then given \(q\) queries. For each query, provided an integer \(k_j\), you must, for every interval in the sequence, compute the number of other intervals (excluding itself) that are \(k_j\)-similar.

Note: Pay special attention to the memory limitations imposed by the problem.

inputFormat

The first line contains three integers \(n\), \(l\), and \(q\) (with \(1\le l\le n\) and \(1\le q\le 10^5\)).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the lottery numbers.

Each of the following \(q\) lines contains a single integer \(k_j\): the similarity threshold for that query.

outputFormat

For each query, output one line containing \(n-l+1\) integers. The \(i\)-th integer on the line indicates the number of other intervals that are \(k_j\)-similar to the \(i\)-th interval.

sample

5 3 2
1 2 3 2 3
0
1

0 0 0
1 0 1

</p>