#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721;
const int MAXN = 100003;
int n, q, a[MAXN];
void read() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i], a[i] %= MOD;
  cin >> q;
}
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
int tr[MAXN * 4][49], lazy[MAXN * 4];
void merge(int v) {
  for (int i = 0; i <= 47; i++) tr[v][i] = add(tr[v * 2][i], tr[v * 2 + 1][i]);
}
int nxt[49];
void push(int v, int l, int r) {
  lazy[v] %= 48;
  for (int i = 0; i <= 47; i++) nxt[i] = tr[v][(i + lazy[v]) % 48];
  for (int i = 0; i <= 47; i++) tr[v][i] = nxt[i];
  if (l != r) lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];
  lazy[v] = 0;
}
void build(int v, int l, int r) {
  if (l == r) {
    tr[v][0] = a[l];
    for (int i = 1; i <= 47; i++)
      tr[v][i] = (long long)tr[v][i - 1] * (long long)tr[v][i - 1] % MOD *
                 (long long)tr[v][i - 1] % MOD;
    return;
  }
  int mid = (l + r) / 2;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  merge(v);
}
void update(int v, int l, int r, int ll, int rr) {
  push(v, l, r);
  if (l > rr || r < ll) return;
  if (l >= ll && r <= rr) {
    lazy[v]++;
    push(v, l, r);
    return;
  }
  int mid = (l + r) / 2;
  update(v * 2, l, mid, ll, rr);
  update(v * 2 + 1, mid + 1, r, ll, rr);
  merge(v);
}
int get(int v, int l, int r, int ll, int rr) {
  push(v, l, r);
  if (l > rr || r < ll) return 0;
  if (l >= ll && r <= rr) return tr[v][0];
  int mid = (l + r) / 2;
  return add(get(v * 2, l, mid, ll, rr), get(v * 2 + 1, mid + 1, r, ll, rr));
}
void solve() {
  build(1, 1, n);
  while (q--) {
    int type, l, r;
    cin >> type >> l >> r;
    if (type == 1)
      cout << get(1, 1, n, l, r) << endl;
    else
      update(1, 1, n, l, r);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  read();
  solve();
}
