#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int x, y;
  y = scanf("%d", &x);
  return x;
}
const int N = 1e5 + 123;
const int T = 48;
const int mod = 95542721;
int seg[N * 8][T], lazy[N * 8], a[N][T], b[N];
int n;
void add(int &a, long long b) { a = (a + b) % mod; }
void mul(int &a, long long b) { a = (a * b) % mod; }
void build(int x = 1, int l = 0, int r = n) {
  if (l + 1 == r) {
    for (int i = 0; i < (T); i++) seg[x][i] = a[l][i];
    return;
  }
  int m = l + r >> 1;
  build(x * 2 + 0, l, m);
  build(x * 2 + 1, m, r);
  for (int i = 0; i < (T); i++)
    seg[x][i] = (seg[x * 2][i] + seg[x * 2 + 1][i]) % mod;
}
void push(int x) {
  rotate(seg[x * 2 + 0], seg[x * 2 + 0] + lazy[x] % T, seg[x * 2 + 0] + T);
  rotate(seg[x * 2 + 1], seg[x * 2 + 1] + lazy[x] % T, seg[x * 2 + 1] + T);
  lazy[x * 2 + 0] += lazy[x];
  lazy[x * 2 + 1] += lazy[x];
  lazy[x] = 0;
}
long long get(int l, int r, int x = 1, int ld = 0, int rd = n) {
  if (l <= ld and rd <= r) return seg[x][0];
  push(x);
  int m = ld + rd >> 1, ans = 0;
  if (l < m) add(ans, get(l, r, x * 2 + 0, ld, m));
  if (r > m) add(ans, get(l, r, x * 2 + 1, m, rd));
  return ans;
}
void change(int l, int r, int x = 1, int ld = 0, int rd = n) {
  if (l <= ld and rd <= r) {
    rotate(seg[x], seg[x] + 1, seg[x] + T);
    lazy[x]++;
    push(x);
    return;
  }
  push(x);
  int m = ld + rd >> 1;
  if (l < m) change(l, r, x * 2 + 0, ld, m);
  if (r > m) change(l, r, x * 2 + 1, m, rd);
  for (int i = 0; i < (T); i++)
    seg[x][i] = (seg[x * 2][i] + seg[x * 2 + 1][i]) % mod;
}
int main() {
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<long long> distr;
  ios_base::sync_with_stdio(0), cin.tie(0);
  int q;
  cin >> n;
  for (int i = 0; i < (n); i++) {
    int t;
    cin >> t;
    b[i] = t;
    for (int j = 0; j < (T); j++) {
      a[i][j] = t;
      mul(t, (long long)t * t % mod);
    }
  }
  build();
  cin >> q;
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    l--;
    if (t == 1) {
      cout << get(l, r) << endl;
    } else {
      change(l, r);
    }
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
