Обратите внимание на нестандартное ограничение по памяти.

Уже долгое время вы — фанат Байтлото. Примерно столько же времени ваши родственники говорят вам, что все такие игры — это пустая трата денег. Вы уверены, что это так из-за их неумения играть! У вас есть идеальный план, и скоро все увидят, как вы выигрываете.

Есть много типов игр. Вы интересуетесь в одном из них: Битлото. Выбор был прост, так как это самый простой из предлагаемых типов игр: каждый день случайно выпадает ровно одно число. Вы записываете эти числа за \(n\) последовательных дней и получаете последовательность \(a_1, a_2, \ldots, a_n\). Вы уверены, что в этой последовательности есть какая-то закономерность, а именно, в отрезках из \(l\) последовательных дней. Ваша семья всё ещё не верит вам, так что единственный способ убедить их — это использовать серьёзную математику.

Есть \(n - l + 1\) отрезок дней длины \(l\). \(i\)-й отрезок начинается в позиции \(i\) и содержит элементы \(a_i, a_{i + 1}, \ldots, a_{i + l - 1}\). Расстояние между двумя отрезками — это количество несовпадающих элементов на соответствующих позициях. Другими словами, для отрезков \(x\) и \(y\) это количество таких \(i\) (\(0 \leq i < l\)), что \(a_{x + i}\) и \(a_{y + i}\) различны. И наконец, будем говорить, что два отрезка \(k\)-похожи, если расстояние между ними не превосходит \(k\).

Зафиксированы последовательность и число \(l\). Вам даны \(q\) запросов. В каждом запросе вам дано число \(k_j\) и для каждого из \(n - l + 1\) отрезов вы должны найти количество отрезков той же длины, которые \(k\)-похожи на данный (не считая сам этот отрезок).