#include <bits/stdc++.h>
using namespace std;
struct node {
  node *L, *R;
  int p, num, l, r, m, v[48];
  node() {}
  node(int x, int y) {
    L = R = 0;
    p = num = 0;
    l = x;
    r = y;
    m = (l + r) >> 1;
  }
};
int a[100001];
node *root;
void update(node *it) {
  for (int i = 0; i < 48; i++)
    it->v[(i + it->p) % 48] =
        (it->L->v[(i + it->L->p) % 48] + it->R->v[(i + it->R->p) % 48]) %
        95542721;
}
void clear(node *it) {
  if (!it->num) return;
  it->L->p += it->num;
  it->L->num += it->num;
  it->R->p += it->num;
  it->R->num += it->num;
  it->num = 0;
}
node *build(int l, int r) {
  node *it = new node(l, r);
  if (l == r) {
    it->v[0] = a[l] % 95542721;
    for (int i = 1; i < 48; i++)
      it->v[i] = (long long)it->v[i - 1] * it->v[i - 1] % 95542721 *
                 it->v[i - 1] % 95542721;
  } else {
    it->L = build(l, it->m);
    it->R = build(it->m + 1, r);
    update(it);
  }
  return it;
}
int query(node *it, int l, int r) {
  if (it->l == l && it->r == r) return it->v[it->p % 48];
  clear(it);
  if (r <= it->m) return query(it->L, l, r);
  if (l > it->m) return query(it->R, l, r);
  return (query(it->L, l, it->m) + query(it->R, it->m + 1, r)) % 95542721;
}
void modify(node *it, int l, int r) {
  if (it->l == l && it->r == r) {
    it->p++;
    it->num++;
    return;
  }
  clear(it);
  if (r <= it->m)
    modify(it->L, l, r);
  else if (l > it->m)
    modify(it->R, l, r);
  else {
    modify(it->L, l, it->m);
    modify(it->R, it->m + 1, r);
  }
  update(it);
}
int main() {
  int n, q, i, x, y;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", a + i);
  root = build(1, n);
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d", &i, &x, &y);
    if (i == 1)
      printf("%d\n", query(root, x, y));
    else
      modify(root, x, y);
  }
  return 0;
}
