#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 95542721;
int seg[maxn * 4][100], lazy[maxn * 4], a[maxn];
void update(int v) {
  for (int i = 0; i < 48; i++)
    seg[v][i] = (seg[v * 2][i] + seg[v * 2 + 1][i]) % mod;
}
void build(int v, int l, int r, int x, long long val) {
  if (r - l == 1) {
    seg[v][0] = val;
    for (int i = 1; i < 48; i++)
      seg[v][i] =
          1LL * seg[v][i - 1] * seg[v][i - 1] % mod * seg[v][i - 1] % mod;
    return;
  }
  int mid = (l + r) / 2;
  if (x < mid)
    build(v * 2, l, mid, x, val);
  else
    build(v * 2 + 1, mid, r, x, val);
}
void mergee(int v, int l, int r) {
  if (r - l == 1) return;
  int mid = (l + r) / 2;
  mergee(v * 2, l, mid);
  mergee(v * 2 + 1, mid, r);
  update(v);
}
void shift(int v) {
  lazy[v * 2] = (lazy[v * 2] + lazy[v]) % 48;
  lazy[v * 2 + 1] = (lazy[v * 2 + 1] + lazy[v]) % 48;
  for (int j = 0; j < lazy[v]; j++)
    seg[v * 2][48 + j] = seg[v * 2][j],
                    seg[v * 2 + 1][48 + j] = seg[v * 2 + 1][j];
  for (int i = 0; i < 48; i++)
    seg[v * 2][i] = seg[v * 2][i + lazy[v]],
            seg[v * 2 + 1][i] = seg[v * 2 + 1][i + lazy[v]];
  lazy[v] = 0;
}
void add(int v, int l, int r, int b, int e) {
  if (e <= l || r <= b) return;
  if (b <= l && r <= e) {
    seg[v][48] = seg[v][0];
    for (int i = 0; i < 48; i++) seg[v][i] = seg[v][i + 1];
    lazy[v] = (lazy[v] + 1) % 48;
    return;
  }
  int mid = (l + r) / 2;
  shift(v);
  add(v * 2, l, mid, b, e);
  add(v * 2 + 1, mid, r, b, e);
  update(v);
}
long long query(int v, int l, int r, int b, int e) {
  if (e <= l || r <= b) return 0;
  if (b <= l && r <= e) return seg[v][0];
  int mid = (l + r) / 2;
  shift(v);
  update(v);
  return (query(v * 2, l, mid, b, e) + query(v * 2 + 1, mid, r, b, e)) % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) build(1, 0, n, i, a[i]);
  mergee(1, 0, n);
  int q;
  cin >> q;
  while (q--) {
    int l, r, c;
    cin >> c >> l >> r;
    l--;
    if (c == 1)
      cout << query(1, 0, n, l, r) << endl;
    else
      add(1, 0, n, l, r);
  }
  return 0;
}
