#include <bits/stdc++.h>   using namespace std;   struct arr {     int l, r, add, cnt, sum[50];   } a[110005 * 4];   int data[110005], i, n, m, opt, L, R;   const int P = 95542721;   inline int calc(int x) {     while (x > 47) x -= 48;     return x;   }   inline void down(int k) {     if (!a[k].cnt || a[k].l == a[k].r) return;     int W = a[k].cnt;     a[k].cnt = 0;     a[(k << 1)].add = calc(a[(k << 1)].add + W);     a[(k << 1)].cnt = calc(a[(k << 1)].cnt + W);     a[(k << 1 | 1)].add = calc(a[(k << 1 | 1)].add + W);     a[(k << 1 | 1)].cnt = calc(a[(k << 1 | 1)].cnt + W);   }   inline void up(int k) {     for (int i = 0; i < 48; i++)       a[k].sum[i] = (a[(k << 1)].sum[calc(a[(k << 1)].add + i)] +                      a[(k << 1 | 1)].sum[calc(a[(k << 1 | 1)].add + i)]) %                     P;   }   void build(int k, int l, int r) {     a[k].l = l;     a[k].r = r;     a[k].add = a[k].cnt = 0;     if (l == r) {       a[k].sum[0] = data[l];       for (int i = 1; i <= 47; i++)         a[k].sum[i] = (a[k].sum[i - 1] * 1ll * a[k].sum[i - 1] % P * 1ll *                        a[k].sum[i - 1] % P);       return;     }     int mid = (l + r) >> 1;     if (l <= mid) build((k << 1), l, mid);     if (r > mid) build((k << 1 | 1), mid + 1, r);     for (int i = 0; i < 48; i++)       a[k].sum[i] = (a[(k << 1)].sum[i] + a[(k << 1 | 1)].sum[i]) % P;   }   void update(int k) {     if (L <= a[k].l && a[k].r <= R) {       a[k].cnt = calc(a[k].cnt + 1);       a[k].add = calc(a[k].add + 1);       return;     }     down(k);     int mid = (a[k].l + a[k].r) >> 1;     if (L <= mid) update((k << 1));     if (R > mid) update((k << 1 | 1));     a[k].add = 0;     up(k);   }   int Query(int k) {     if (L <= a[k].l && a[k].r <= R) return a[k].sum[calc(a[k].add)];     down(k);     int res = 0;     int mid = (a[k].l + a[k].r) >> 1;     if (L <= mid) res = Query((k << 1));     if (R > mid) (res += Query((k << 1 | 1))) %= P;     return res;   }   int main() {     scanf( %d , &n);     for (i = 1; i <= n; i++) scanf( %d , &data[i]);     build(1, 1, n);     scanf( %d , &m);     while (m--) {       scanf( %d%d%d , &opt, &L, &R);       if (opt == 1)         printf( %d n , Query(1));       else         update(1);     }     return 0;   }   