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 $a_1,a_2,...,a_n$. 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 $a_i,a_{i+1},...,a_{i+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 $a_{x+i}$ and $a_{y+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 $k_j$ and for each of the $n − l + 1$ intervals you must find the number of intervals of the same length that are $k_j$-similar to this interval (not counting this interval itself).
Comet OJ