#include <bits/stdc++.h>
using namespace std;
const int maxn = 100200;
const long long mod = 95542721;
const int nn = 48;
struct node {
  vector<long long> values;
  int loop;
  node() {}
  node(bool h) : values(nn), loop(0) {}
};
node tree[maxn << 2];
long long arr[maxn];
node merge(node &a, node &b) {
  node ans(true);
  for (int e = 0; e < nn; e++)
    ans.values[e] =
        (a.values[(a.loop + e) % nn] + b.values[(b.loop + e) % nn]) % mod;
  return ans;
}
void build(int id, int l, int r) {
  if (l == r) {
    tree[id].values.resize(nn);
    tree[id].values[0] = arr[l] % mod;
    for (int e = 1; e < nn; e++)
      tree[id].values[e] =
          (((tree[id].values[e - 1] * tree[id].values[e - 1]) % mod) *
           tree[id].values[e - 1]) %
          mod;
    assert((((tree[id].values[nn - 1] * tree[id].values[nn - 1]) % mod) *
            tree[id].values[nn - 1]) %
               mod ==
           arr[l] % mod);
  } else {
    build((id << 1), l, ((l + r) >> 1));
    build(((id << 1) | 1), ((l + r) >> 1) + 1, r);
    tree[id] = merge(tree[(id << 1)], tree[((id << 1) | 1)]);
  }
}
void push(int id, int l, int r) {
  if (tree[id].loop) {
    node ans(true);
    for (int e = 0; e < nn; e++)
      ans.values[e] = tree[id].values[(tree[id].loop + e) % nn];
    if (l != r) {
      tree[(id << 1)].loop += tree[id].loop;
      tree[(id << 1)].loop %= nn;
      tree[((id << 1) | 1)].loop += tree[id].loop;
      tree[((id << 1) | 1)].loop %= nn;
    }
    tree[id] = ans;
  }
}
void update(int id, int l, int r, int x, int y) {
  push(id, l, r);
  if (l > y || r < x) return;
  if (x <= l && r <= y) {
    tree[id].loop += 1;
    push(id, l, r);
    return;
  }
  update((id << 1), l, ((l + r) >> 1), x, y);
  update(((id << 1) | 1), ((l + r) >> 1) + 1, r, x, y);
  tree[id] = merge(tree[(id << 1)], tree[((id << 1) | 1)]);
}
long long query(int id, int l, int r, int x, int y) {
  push(id, l, r);
  if (l > y || r < x) return 0ll;
  if (x <= l && r <= y) return tree[id].values[0];
  return (query((id << 1), l, ((l + r) >> 1), x, y) +
          query(((id << 1) | 1), ((l + r) >> 1) + 1, r, x, y)) %
         mod;
}
int main() {
  int n;
  cin >> n;
  for (int e = 0; e < n; e++) cin >> arr[e];
  build(1, 0, n - 1);
  int m;
  cin >> m;
  for (int e = 0; e < m; e++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == 1)
      cout << query(1, 0, n - 1, b - 1, c - 1) << endl;
    else
      update(1, 0, n - 1, b - 1, c - 1);
  }
  return 0;
}
