#include <bits/stdc++.h>
using namespace std;
int ch[920000][51], i, j, k, l, n, m, x, y, a[920000], sta[920000], ans, type;
int P3(int x) { return (long long)x * x % 95542721 * x % 95542721; }
void renew(int p, int p1, int p2) {
  for (int i = 0; i <= 47; ++i) {
    ch[p][i] = ch[p1][i] + ch[p2][i];
    if (ch[p][i] >= 95542721) ch[p][i] -= 95542721;
  }
}
void build(int p, int l, int r) {
  int mid = (l + r) / 2;
  if (l == r) {
    ch[p][0] = a[l] % 95542721;
    for (int i = 1; i <= 47; ++i) ch[p][i] = P3(ch[p][i - 1]);
    return;
  }
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  renew(p, p * 2, p * 2 + 1);
}
void modify(int p, int k) {
  int d[50] = {0};
  for (int i = 0; i <= 47; ++i) d[i] = ch[p][(i + k) % 48];
  for (int i = 0; i <= 47; ++i) ch[p][i] = d[i];
  sta[p] = (sta[p] + k) % 48;
}
void updata(int p) {
  if (sta[p]) {
    modify(p * 2, sta[p]);
    modify(p * 2 + 1, sta[p]);
    sta[p] = 0;
  }
}
void add(int p, int l, int r, int x, int y) {
  int mid = (l + r) / 2;
  if (x <= l && y >= r) {
    modify(p, 1);
    return;
  }
  updata(p);
  if (x <= mid) add(p * 2, l, mid, x, y);
  if (y > mid) add(p * 2 + 1, mid + 1, r, x, y);
  renew(p, p * 2, p * 2 + 1);
}
void calc(int p, int l, int r, int x, int y) {
  int mid = (l + r) / 2;
  if (x <= l && y >= r) {
    ans = (ans + ch[p][0]) % 95542721;
    return;
  }
  updata(p);
  if (x <= mid) calc(p * 2, l, mid, x, y);
  if (y > mid) calc(p * 2 + 1, mid + 1, r, x, y);
  renew(p, p * 2, p * 2 + 1);
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  build(1, 1, n);
  scanf("%d", &m);
  for (i = 1; i <= m; ++i) {
    scanf("%d%d%d", &type, &x, &y);
    if (type == 1) {
      ans = 0;
      calc(1, 1, n, x, y);
      printf("%d\n", ans);
    } else {
      add(1, 1, n, x, y);
    }
  }
}
