Виктория очень часто обижается на Лёшу. Обижалась она и в этот раз. Известно, что Лёша и Виктория гуляли n минут. И в каждую из этих минут Виктория была либо обижена, либо не обижена на Лёшу. Так как все мы программисты, то будем обозначать эти n минут состояния Виктории как n-битную строку. Более формально i-й бит строки будет равен единице, если она обижалась в i-ю минуту, иначе этот бит будет равен нулю.

Лёша утверждает Виктории, что она слишком часто на него обижается. Он любит всё доказывать. Поэтому Лёша хочет посчитать количество таких отрезков времени, на которых её обида была строго больше, чем число X. За отрезок может отвечать пара чисел (l, r), где 1 ≤ l ≤ r ≤ n. Обида Виктории на отрезке — это отношение количества минут, которые она обижалась, к общему количеству минут на отрезке. Более формально обида Виктории на отрезке (l, r) равна , где cnt₁ — количество единиц на отрезке (l, r) битовой строки, а cnt_all — общее количество символов с позиции l по r в битовой строке.

Помогите Лёше доказать Виктории, что обид слишком много!