#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 95542721;
const double eps = 1e-6;
const double PI = acos(-1);
int n, q;
int a[N << 2][48], lazy[N << 2];
inline void pull(int rt) {
  for (int i = 0; i < 48; i++) {
    a[rt][i] = a[rt << 1][i] + a[rt << 1 | 1][i];
    if (a[rt][i] >= mod) a[rt][i] -= mod;
  }
}
inline void push(int rt) {
  lazy[rt] %= 48;
  if (lazy[rt]) {
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    rotate(a[rt << 1], a[rt << 1] + lazy[rt], a[rt << 1] + 48);
    rotate(a[rt << 1 | 1], a[rt << 1 | 1] + lazy[rt], a[rt << 1 | 1] + 48);
    lazy[rt] = 0;
  }
}
void build(int l, int r, int rt) {
  if (l == r) {
    scanf("%d", &a[rt][0]);
    a[rt][0] %= mod;
    for (int i = 1; i < 48; i++)
      a[rt][i] = 1LL * a[rt][i - 1] * a[rt][i - 1] % mod * a[rt][i - 1] % mod;
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  pull(rt);
}
void update(int L, int R, int l, int r, int rt) {
  if (l >= L && r <= R) {
    lazy[rt]++;
    rotate(a[rt], a[rt] + 1, a[rt] + 48);
    return;
  }
  push(rt);
  int mid = l + r >> 1;
  if (L <= mid) update(L, R, l, mid, rt << 1);
  if (R > mid) update(L, R, mid + 1, r, rt << 1 | 1);
  pull(rt);
}
int query(int L, int R, int l, int r, int rt) {
  if (l >= L && r <= R) return a[rt][0];
  push(rt);
  int mid = l + r >> 1;
  if (R <= mid)
    return query(L, R, l, mid, rt << 1);
  else if (L > mid)
    return query(L, R, mid + 1, r, rt << 1 | 1);
  else
    return (query(L, R, l, mid, rt << 1) +
            query(L, R, mid + 1, r, rt << 1 | 1)) %
           mod;
}
int main() {
  scanf("%d", &n);
  build(1, n, 1);
  scanf("%d", &q);
  while (q--) {
    int t, L, R;
    scanf("%d%d%d", &t, &L, &R);
    if (t == 1) {
      printf("%d\n", query(L, R, 1, n, 1));
    } else {
      update(L, R, 1, n, 1);
    }
  }
  return 0;
}
