#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721;
const int BUCKET = 10;
long long dat[100005], ans[100005][50];
int tms[100005];
void realise(int buc, int cl, int cr) {
  for (int i = cl; i <= cr; i++) {
    long long ci = dat[i];
    for (int j = 0; j < 48; j++) {
      ans[buc][j] -= ci;
      if (ans[buc][j] < 0) ans[buc][j] += MOD;
      ci = ci * ci % MOD * ci % MOD;
    }
  }
  for (int i = cl; i <= cr; i++) {
    dat[i] = dat[i] * dat[i] % MOD * dat[i] % MOD;
    long long ci = dat[i];
    for (int j = 0; j < 48; j++) {
      ans[buc][j] += ci;
      if (ans[buc][j] >= MOD) ans[buc][j] -= MOD;
      ci = ci * ci % MOD * ci % MOD;
    }
  }
}
void modify(int l, int r) {
  int lb = l / BUCKET, rb = r / BUCKET;
  if (lb == rb)
    realise(lb, l, r);
  else {
    realise(lb, l, lb * BUCKET + BUCKET - 1);
    realise(rb, rb * BUCKET, r);
    for (int k = lb + 1; k < rb; k++) {
      tms[k]++;
      if (tms[k] >= 48) tms[k] -= 48;
    }
  }
}
long long brute(int buc, int cl, int cr) {
  long long res = 0LL;
  for (int i = cl; i <= cr; i++) {
    long long ci = dat[i];
    for (int j = 0; j < (tms[buc]); j++) ci = ci * ci % MOD * ci % MOD;
    res += ci;
  }
  return res % MOD;
}
long long query(int l, int r) {
  int lb = l / BUCKET, rb = r / BUCKET;
  long long res = 0LL;
  if (lb == rb)
    res = brute(lb, l, r);
  else {
    res = brute(lb, l, lb * BUCKET + BUCKET - 1) + brute(rb, rb * BUCKET, r);
    for (int k = lb + 1; k < rb; k++) res += ans[k][tms[k]];
  }
  res %= MOD;
  if (res < 0) res += MOD;
  return res;
}
int main() {
  int n, q, t, l, r;
  scanf("%d", &n);
  for (int k = 0; k < (n); k++) scanf("%I64d", &dat[k]);
  for (int i = 0; i < (n); i++) {
    int buc = i / BUCKET;
    long long ci = dat[i];
    for (int j = 0; j < (48); j++) {
      ans[buc][j] += ci;
      if (ans[buc][j] >= MOD) ans[buc][j] -= MOD;
      ci = ci * ci % MOD * ci % MOD;
    }
  }
  scanf("%d", &q);
  for (int k = 0; k < (q); k++) {
    scanf("%d%d%d", &t, &l, &r);
    l--;
    r--;
    if (t == 1)
      printf("%I64d\n", query(l, r));
    else
      modify(l, r);
  }
  return 0;
}
