#include <bits/stdc++.h>
using namespace std;
const int N = 110010;
const int mod = 95542721;
int val[48][N << 2];
int cov[N << 2];
int a[N], tmp[50];
void up(int idx) {
  for (int i = 0; i < 48; ++i) {
    val[i][idx] = (val[i][idx << 1] + val[i][idx << 1 | 1]) % mod;
  }
}
void gao(int idx, int step) {
  step %= 48;
  for (int i = 0; i < 48; ++i) tmp[i] = val[i][idx];
  for (int i = 0; i < 48; ++i) val[i][idx] = tmp[(i + step) % 48];
}
void down(int idx) {
  if (cov[idx] != 0) {
    gao(idx << 1, cov[idx]);
    gao(idx << 1 | 1, cov[idx]);
    cov[idx << 1] += cov[idx];
    cov[idx << 1 | 1] += cov[idx];
    cov[idx] = 0;
  }
}
void build(int l, int r, int idx) {
  if (l == r) {
    val[0][idx] = a[l];
    for (int i = 1; i < 48; ++i) {
      val[i][idx] = (long long)val[i - 1][idx] * val[i - 1][idx] % mod;
      val[i][idx] = (long long)val[i][idx] * val[i - 1][idx] % mod;
    }
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, idx << 1);
  build(m + 1, r, idx << 1 | 1);
  up(idx);
}
int query(int l, int r, int L, int R, int idx) {
  if (l >= L && r <= R) {
    return val[0][idx];
  }
  down(idx);
  int m = (l + r) >> 1;
  if (m < L) {
    return query(m + 1, r, L, R, idx << 1 | 1);
  } else if (m >= R) {
    return query(l, m, L, R, idx << 1);
  } else {
    return (query(l, m, L, m, idx << 1) +
            query(m + 1, r, m + 1, R, idx << 1 | 1)) %
           mod;
  }
}
void update(int l, int r, int L, int R, int idx) {
  if (l >= L && r <= R) {
    cov[idx]++;
    gao(idx, 1);
    return;
  }
  down(idx);
  int m = (l + r) >> 1;
  if (m < L) {
    update(m + 1, r, L, R, idx << 1 | 1);
  } else if (m >= R) {
    update(l, m, L, R, idx << 1);
  } else {
    update(l, m, L, m, idx << 1);
    update(m + 1, r, m + 1, R, idx << 1 | 1);
  }
  up(idx);
}
int main(void) {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  build(1, n, 1);
  int m, op, x, y;
  scanf("%d", &m);
  while (m--) {
    scanf("%d %d %d", &op, &x, &y);
    if (op == 1) {
      printf("%d\n", query(1, n, x, y, 1));
    } else {
      update(1, n, x, y, 1);
    }
  }
  return 0;
}
