#include <bits/stdc++.h>
using namespace std;
int n;
long long MOD = 95542721;
long long a[100100];
struct Node {
  vector<long long> v;
  int now;
  Node() {
    v.resize(48);
    now = 0;
  }
  Node(long long val) {
    v.resize(48);
    now = 0;
    v[0] = val;
    for (int i = 1; i < 48; i++)
      v[i] = (((v[i - 1] * v[i - 1]) % MOD) * v[i - 1]) % MOD;
  }
} seg[100100 * 5];
long long lazy[100100 * 5];
void merge(int p) {
  for (int i = 0; i < 48; i++) {
    int Pi = (seg[p].now + i) % 48;
    int Li = (seg[p * 2].now + i) % 48;
    int Ri = (seg[p * 2 + 1].now + i) % 48;
    seg[p].v[Pi] = (seg[p * 2].v[Li] + seg[p * 2 + 1].v[Ri]) % MOD;
  }
}
void pushLazy(int p, int L, int R) {
  if (lazy[p]) {
    if (L != R) {
      lazy[p * 2] += lazy[p];
      lazy[p * 2 + 1] += lazy[p];
    }
    seg[p].now += lazy[p];
    seg[p].now %= 48;
    lazy[p] = 0;
  }
}
void build(int p = 1, int L = 1, int R = n) {
  if (L == R) {
    seg[p] = Node(a[L]);
    return;
  }
  int mid = (L + R) / 2;
  build(p * 2, L, mid);
  build(p * 2 + 1, mid + 1, R);
  merge(p);
}
void update(int i, int j, int p = 1, int L = 1, int R = n) {
  pushLazy(p, L, R);
  if (L > j || R < i) return;
  if (L >= i && R <= j) {
    lazy[p]++;
    pushLazy(p, L, R);
    return;
  }
  int mid = (L + R) / 2;
  update(i, j, p * 2, L, mid);
  update(i, j, p * 2 + 1, mid + 1, R);
  merge(p);
}
long long query(int i, int j, int p = 1, int L = 1, int R = n) {
  pushLazy(p, L, R);
  if (L > j || R < i) return 0;
  if (L >= i && R <= j) return seg[p].v[seg[p].now];
  int mid = (L + R) / 2;
  long long c1 = query(i, j, p * 2, L, mid);
  long long c2 = query(i, j, p * 2 + 1, mid + 1, R);
  return (c1 + c2) % MOD;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build();
  int q;
  cin >> q;
  while (q--) {
    int t;
    cin >> t;
    long long L, R;
    cin >> L >> R;
    if (t == 1) {
      long long ans = query(L, R);
      cout << ans << endl;
    } else {
      update(L, R);
    }
  }
  return 0;
}
