D - Lowbit

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
const int mod = 998244353;

ll lowbit(ll x)
{
    return x & (-x);
}

int count(ll x)
{
    if(lowbit(x) != x)
        return 1;
    return 0;
}

struct node
{
    int l, r;
    ll mul;
    ll sum;
    ll num;
} tr[N * 4];

ll a[N];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].num = tr[u << 1].num + tr[u << 1 | 1].num;
}

void pushdown(int u)
{
    auto &root = tr[u], &lson = tr[u << 1], &rson = tr[u << 1 | 1];
    if(!root.mul)
        return ;
    lson.mul = lson.mul * root.mul % mod;
    rson.mul = rson.mul * root.mul % mod;
    lson.sum = lson.sum * root.mul % mod;
    rson.sum = rson.sum * root.mul % mod;
    root.mul = 1;
}

void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, 1, a[l], count(a[l])};
        return;
    }
    tr[u] = {l, r, 1, 0, 0};
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r)
{
//    cout << u << ' ' << tr[u].l << ' ' << tr[u].r << ' ' << tr[u].num << endl;
    if(tr[u].l >= l && tr[u].r <= r && tr[u].num <= 0)
    {
        tr[u].sum = 2 * (tr[u].sum % mod) % mod;
        tr[u].mul = 2 * (tr[u].mul % mod) % mod;
    }
    else if(tr[u].l == tr[u].r && tr[u].num > 0)
    {
        tr[u].sum = lowbit(tr[u].sum) + tr[u].sum;
        tr[u].num = count(tr[u].sum);
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid)
        {
            modify(u << 1, l, r);
        }
        if(r > mid)
        {
            modify(u << 1 | 1, l, r);
        }
        pushup(u);
    }
}

ll query(int u, int l, int r)
{
//    cout << u << ' ' << tr[u].l << ' ' << tr[u].r << endl;
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum % mod;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll res = 0;
    if(l <= mid)
        res = query(u << 1, l, r) % mod;
    if(r > mid)
        res = (res + query(u << 1 | 1, l, r) % mod) % mod;
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, q;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", a + i);
        }
        build(1, 1, n);
        scanf("%d", &q);
        for(int i = 1, op, l, r; i <= n; i++)
        {
            scanf("%d%d%d", &op, &l, &r);
            if(op == 1)
            {
                modify(1, l, r);
            }
            else
            {
                printf("%lld\n", query(1, l, r));
            }
        }
    }
    return 0;
}