#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100001, MaxT = 50;
int aux[MaxT], T, N, arr[MaxN];
long long int mod = (95542721);
struct node {
  long long int sum[MaxT], L;
  void shift() {
    int i;
    for (i = 0; i < T; i++) aux[i] = sum[(i + L) % T];
    for (i = 0; i < T; i++) sum[i] = aux[i];
  }
};
node ST[MaxN * 4];
void push(int x, int y, int n) {
  if (ST[n].L == 0) return;
  ST[n].shift();
  if (x + 1 != y) {
    ST[2 * n].L += ST[n].L;
    ST[2 * n + 1].L += ST[n].L;
  }
  ST[n].L = 0;
}
long long int qry(int x, int y, int n, int &l, int &r) {
  push(x, y, n);
  if (l <= x && y <= r) return ST[n].sum[0];
  if (y <= l || r <= x) return 0;
  long long int izq, der;
  izq = qry(x, (x + y) / 2, 2 * n, l, r);
  der = qry((x + y) / 2, y, 2 * n + 1, l, r);
  return (izq + der) % mod;
}
void upd(int x, int y, int n, int &l, int &r) {
  push(x, y, n);
  if (l <= x && y <= r) {
    ST[n].L++;
    push(x, y, n);
    return;
  }
  if (y <= l || r <= x) return;
  upd(x, (x + y) / 2, 2 * n, l, r);
  upd((x + y) / 2, y, 2 * n + 1, l, r);
  for (int i = 0; i < T; i++)
    ST[n].sum[i] = (ST[n * 2].sum[i] + ST[n * 2 + 1].sum[i]) % mod;
}
long long int query(int x, int y) {
  x--;
  return qry(0, N, 1, x, y);
}
void update(int x, int y) {
  x--;
  upd(0, N, 1, x, y);
}
void init(int x, int y, int n) {
  if (x + 1 == y) {
    ST[n].sum[0] = arr[x];
    for (int i = 1; i < T; i++) {
      long long int x = ST[n].sum[i - 1];
      ST[n].sum[i] = (((x * x) % mod) * x) % mod;
    }
    return;
  }
  init(x, (x + y) / 2, n * 2);
  init((x + y) / 2, y, n * 2 + 1);
  for (int i = 0; i < T; i++)
    ST[n].sum[i] = (ST[n * 2].sum[i] + ST[n * 2 + 1].sum[i]) % mod;
}
int main() {
  cin.tie(0), ios_base::sync_with_stdio(0);
  int i, j, p, q, M;
  cin >> N;
  T = 1, p = 3;
  while (p % (mod - 1) != 1) {
    p = (3 * p) % (mod - 1);
    T++;
  }
  for (i = 0; i < N; i++) cin >> arr[i];
  init(0, N, 1);
  cin >> M;
  for (i = 0; i < M; i++) {
    cin >> j >> p >> q;
    if (j == 1) cout << query(p, q) << "\n";
    if (j == 2) update(p, q);
  }
}
