#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721, MaxN = 100003, cycle = 48;
int n, q, a[MaxN];
struct Node {
  int offset;
  long long sum[48];
} T[MaxN * 4];
inline void movR(long long a[], const int& k) {
  long long t[48];
  for (int i = 0; i < 48; ++i) t[i] = a[i];
  for (int i = 0; i < 48; ++i) a[i] = t[(i + k) % 48];
}
inline void pushdown(int p) {
  if (T[p].offset) {
    movR(T[p * 2].sum, T[p].offset);
    movR(T[p * 2 + 1].sum, T[p].offset);
    T[p * 2].offset += T[p].offset;
    T[p * 2 + 1].offset += T[p].offset;
    T[p * 2].offset %= 48;
    T[p * 2 + 1].offset %= 48;
    T[p].offset = 0;
  }
}
inline void update(int p) {
  for (int i = 0; i < 48; ++i)
    T[p].sum[i] = (T[p * 2].sum[i] + T[p * 2 + 1].sum[i]) % MOD;
}
void build(int p, int l, int r) {
  if (l == r) {
    T[p].sum[0] = a[l];
    for (int i = 1; i < 48; ++i)
      T[p].sum[i] =
          T[p].sum[i - 1] * T[p].sum[i - 1] % MOD * T[p].sum[i - 1] % MOD;
    return;
  }
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  update(p);
}
void modify(int x, int p, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    T[p].offset += x;
    movR(T[p].sum, x);
    T[p].offset %= 48;
    return;
  }
  pushdown(p);
  int mid = (l + r) / 2;
  if (ll <= mid) modify(x, p * 2, l, mid, ll, rr);
  if (rr > mid) modify(x, p * 2 + 1, mid + 1, r, ll, rr);
  update(p);
}
long long query(int p, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) return T[p].sum[0];
  pushdown(p);
  int mid = (l + r) / 2;
  long long ret = 0;
  if (ll <= mid) ret += query(p * 2, l, mid, ll, rr);
  if (rr > mid) ret += query(p * 2 + 1, mid + 1, r, ll, rr);
  return ret % MOD;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  build(1, 1, n);
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int type, l, r;
    scanf("%d%d%d", &type, &l, &r);
    if (type == 1) printf("%lld\n", query(1, 1, n, l, r));
    if (type == 2) modify(1, 1, 1, n, l, r);
  }
  return 0;
}
