#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721;
const int MAX = 100005;
int seg[4 * MAX][48], mark[4 * MAX], tmp[48], a[MAX];
int n, q;
int next(int x) { return 1ll * x * x % MOD * x % MOD; }
void fix(int& x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
void merge(int v) {
  for (int i = 0; i < 48; i++) {
    seg[v][i] = seg[2 * v][i] + seg[2 * v + 1][i];
    fix(seg[v][i]);
  }
}
void rotate(int v, int k) {
  for (int i = 0; i < 48; i++) tmp[i] = seg[v][(i + k) % 48];
  for (int i = 0; i < 48; i++) seg[v][i] = tmp[i];
}
void shift(int v) {
  mark[v] %= 48;
  if (mark[v]) {
    rotate(2 * v, mark[v]);
    rotate(2 * v + 1, mark[v]);
    mark[2 * v] += mark[v];
    mark[2 * v + 1] += mark[v];
    mark[v] = 0;
  }
}
void build(int v = 1, int s = 0, int e = n) {
  if (e - s < 2) {
    seg[v][0] = a[s];
    for (int i = 1; i < 48; i++) seg[v][i] = next(seg[v][i - 1]);
    return;
  }
  int mid = (s + e) / 2;
  build(2 * v, s, mid);
  build(2 * v + 1, mid, e);
  merge(v);
}
void upd(int l, int r, int v = 1, int s = 0, int e = n) {
  if (l <= s && e <= r) {
    mark[v]++;
    rotate(v, 1);
    return;
  }
  if (e <= l || r <= s) return;
  shift(v);
  int mid = (s + e) / 2;
  upd(l, r, 2 * v, s, mid);
  upd(l, r, 2 * v + 1, mid, e);
  merge(v);
}
int get(int l, int r, int v = 1, int s = 0, int e = n) {
  if (l <= s && e <= r) return seg[v][0];
  if (e <= l || r <= s) return 0;
  shift(v);
  int mid = (s + e) / 2;
  int ans = get(l, r, 2 * v, s, mid) + get(l, r, 2 * v + 1, mid, e);
  fix(ans);
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] %= MOD;
  }
  build();
  cin >> q;
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    l--;
    if (t == 2)
      upd(l, r);
    else
      cout << get(l, r) << endl;
  }
  return 0;
}
