#include <bits/stdc++.h>
using namespace std;
typedef struct segment_st {
  int lazy;
  int left, right;
  long long value[48];
} SegmentTree;
SegmentTree tree[400005];
void updateDown(int at) {
  tree[at * 2].lazy += tree[at].lazy;
  tree[at * 2 + 1].lazy += tree[at].lazy;
  tree[at * 2].lazy %= 48;
  tree[at * 2 + 1].lazy %= 48;
  tree[at].lazy = 0;
}
void updateUp(int at) {
  updateDown(at);
  for (int i = 0; i < 48; i++) {
    tree[at].value[i] =
        tree[at * 2].value[(i + tree[at * 2].lazy) % 48] +
        tree[at * 2 + 1].value[(i + tree[at * 2 + 1].lazy) % 48];
    tree[at].value[i] %= 95542721;
  }
}
void build_tree(int at, int ll, int rr) {
  tree[at].left = ll;
  tree[at].right = rr;
  tree[at].lazy = 0;
  if (ll == rr) {
    cin >> tree[at].value[0];
    tree[at].value[0] %= 95542721;
    for (int i = 1; i < 48; i++) {
      tree[at].value[i] =
          (((tree[at].value[i - 1] * tree[at].value[i - 1]) % 95542721) *
           tree[at].value[i - 1]) %
          95542721;
    }
  } else {
    int mid = (tree[at].left + tree[at].right) / 2;
    build_tree(at * 2, tree[at].left, mid);
    build_tree(at * 2 + 1, mid + 1, tree[at].right);
    updateUp(at);
  }
}
long long query(int at, int ll, int rr) {
  if (tree[at].left == ll && tree[at].right == rr) {
    return tree[at].value[tree[at].lazy];
  } else {
    updateDown(at);
    long long res = 0;
    int mid = (tree[at].left + tree[at].right) / 2;
    if (ll <= mid) res += query(at * 2, ll, min(rr, mid));
    res %= 95542721;
    if (rr > mid) res += query(at * 2 + 1, max(mid + 1, ll), rr);
    res %= 95542721;
    updateUp(at);
    return res;
  }
}
void update(int at, int ll, int rr, int value) {
  if (tree[at].left == ll && tree[at].right == rr) {
    tree[at].lazy += value;
    tree[at].lazy %= 48;
  } else {
    if (tree[at].lazy) updateDown(at);
    int mid = (tree[at].left + tree[at].right) / 2;
    if (ll <= mid) update(at * 2, ll, min(rr, mid), value);
    if (rr > mid) update(at * 2 + 1, max(mid + 1, ll), rr, value);
    updateUp(at);
  }
}
int main() {
  int N, Q;
  scanf("%d", &N);
  build_tree(1, 1, N);
  scanf("%d", &Q);
  int oper, l, r;
  for (int q = 0; q < Q; q++) {
    scanf("%d %d %d", &oper, &l, &r);
    if (oper == 2) {
      update(1, l, r, 1);
    } else {
      cout << query(1, l, r) << endl;
    }
  }
  return 0;
}
