#include <bits/stdc++.h>
const int mod = 95542721, MAXN = 100002;
int n;
char shi[MAXN * 4];
int s[MAXN * 4][48];
inline int mod_sum(int x, int mod) { return x >= mod ? x - mod : x; }
void __build(int L, int R, int v) {
  if (L == R) {
    scanf("%d", s[v]);
    s[v][0] %= mod;
    for (int i = 0; i < 47; i++)
      s[v][i + 1] = (1LL * s[v][i] * s[v][i]) % mod,
               s[v][i + 1] = (1LL * s[v][i + 1] * s[v][i]) % mod;
  } else {
    __build(L, (L + R) >> 1, (v << 1) + 1);
    __build(((L + R) >> 1) + 1, R, (v << 1) + 2);
    for (int i = 0; i < 48; i++)
      s[v][i] = mod_sum(s[(v << 1) + 1][i] + s[(v << 1) + 2][i], mod);
  }
}
void upd(int l, int r, int L, int R, int v) {
  if (l > R || L > r) return;
  if (l <= L && R <= r) {
    if (++shi[v] == 48) shi[v] = 0;
  } else {
    upd(l, r, L, (L + R) >> 1, (v << 1) + 1);
    upd(l, r, ((L + R) >> 1) + 1, R, (v << 1) + 2);
    for (int i = 0; i < 48; i++)
      s[v][i] = mod_sum(s[(v << 1) + 1][mod_sum(i + shi[(v << 1) + 1], 48)] +
                            s[(v << 1) + 2][mod_sum(i + shi[(v << 1) + 2], 48)],
                        mod);
  }
}
int sum(int l, int r, int L, int R, int v, int ss) {
  if (l > R || L > r) return 0;
  ss = mod_sum(ss + shi[v], 48);
  if (l <= L && R <= r) return s[v][ss];
  return mod_sum(sum(l, r, L, (L + R) >> 1, (v << 1) + 1, ss) +
                     sum(l, r, ((L + R) >> 1) + 1, R, (v << 1) + 2, ss),
                 mod);
}
int main() {
  scanf("%d", &n);
  __build(0, n - 1, 0);
  int test;
  scanf("%d", &test);
  for (; test--;) {
    int t, u, v;
    scanf("%d%d%d", &t, &u, &v);
    if (t == 1) {
      printf("%d\n", sum(u - 1, v - 1, 0, n - 1, 0, 0));
    } else {
      upd(u - 1, v - 1, 0, n - 1, 0);
    }
  }
  return 0;
}
