#include "oriand.h"

#include <algorithm>

long long oriand(int n, int k, std::vector<long long> a)
{
    std::vector<int> orCnts(k, 0);
    std::vector<int> andCnts(k, 0);

    long long ans = 0;
    for (int l = 0, m = -1, r = -1; l < n; l++)
    {
        if (l > 0)
        {
            for (int b = 0; b < k; b++)
            {
                orCnts[b] -= (a[l - 1] >> b) & 1;
            }
        }

        while (m < n && (m < l || std::count(orCnts.begin(), orCnts.end(), 0)))
        {
            m++;

            if (m < n)
            {
                for (int b = 0; b < k; b++)
                {
                    andCnts[b] -= !((a[m] >> b) & 1);
                    orCnts[b] += (a[m] >> b) & 1;
                }
            }
        }

        if (m == n) break;

        while (r < n && (r < m + 1 || std::count(andCnts.begin(), andCnts.end(), 0)))
        {
            r++;

            if (r < n)
            {
                for (int b = 0; b < k; b++)
                {
                    andCnts[b] += !((a[r] >> b) & 1);
                }
            }
        }

        if (r == n) break;

        ans += n - r;
    }

    return ans;
}
