#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721;
int N, Q;
int A[100002];
inline int pow3(int x) { return 1LL * x * x % MOD * x % MOD; }
int ARB[4 * 100002][48], powd[4 * 100002], A1, A2, Av, Ar;
void set_all(int nod, int i1, int i2) {
  if (i1 == i2) {
    ARB[nod][0] = A[i1] % MOD;
    for (int i = 1; i < 48; ++i) ARB[nod][i] = pow3(ARB[nod][i - 1]);
    return;
  }
  int mid = (i1 + i2) / 2;
  set_all(nod * 2, i1, mid);
  set_all(nod * 2 + 1, mid + 1, i2);
  for (int i = 0; i < 48; ++i) {
    ARB[nod][i] = ARB[nod * 2][i] + ARB[nod * 2 + 1][i];
    if (ARB[nod][i] >= MOD) ARB[nod][i] -= MOD;
  }
}
void update(int nod, int i1, int i2) {
  if (A1 <= i1 && i2 <= A2) {
    ++powd[nod];
    return;
  }
  int mid = (i1 + i2) / 2;
  powd[nod * 2] += powd[nod];
  powd[nod * 2 + 1] += powd[nod];
  powd[nod] = 0;
  if (A1 <= mid) update(nod * 2, i1, mid);
  if (A2 > mid) update(nod * 2 + 1, mid + 1, i2);
  for (int i = 0; i < 48; ++i) {
    ARB[nod][i] = ARB[nod * 2][(i + powd[nod * 2]) % 48] +
                  ARB[nod * 2 + 1][(i + powd[nod * 2 + 1]) % 48];
    if (ARB[nod][i] >= MOD) ARB[nod][i] -= MOD;
  }
}
void query(int nod, int i1, int i2) {
  if (A1 <= i1 && i2 <= A2) {
    Ar += ARB[nod][powd[nod] % 48];
    if (Ar >= MOD) Ar -= MOD;
    return;
  }
  int mid = (i1 + i2) / 2;
  powd[nod * 2] += powd[nod];
  powd[nod * 2 + 1] += powd[nod];
  powd[nod] = 0;
  if (A1 <= mid) query(nod * 2, i1, mid);
  if (A2 > mid) query(nod * 2 + 1, mid + 1, i2);
  for (int i = 0; i < 48; ++i) {
    ARB[nod][i] = ARB[nod * 2][(i + powd[nod * 2]) % 48] +
                  ARB[nod * 2 + 1][(i + powd[nod * 2 + 1]) % 48];
    if (ARB[nod][i] >= MOD) ARB[nod][i] -= MOD;
  }
}
int main() {
  cin >> N;
  for (int i = 1; i <= N; ++i) cin >> A[i];
  set_all(1, 1, N);
  cin >> Q;
  for (int i = 1, type, v1, v2; i <= Q; ++i) {
    cin >> type >> v1 >> v2;
    if (type == 2) {
      A1 = v1, A2 = v2;
      update(1, 1, N);
    } else {
      A1 = v1, A2 = v2, Ar = 0;
      query(1, 1, N);
      cout << Ar << '\n';
    }
  }
}
