#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 17);
const int64_t mod = 95542721;
const int period = 48;
inline int64_t cube(int64_t x) { return (((x * x) % mod) * x) % mod; }
int n, m;
int a[MAXN];
struct node {
  int64_t sum[period + 1];
  int lazy;
  node() {
    memset(sum, 0, sizeof(sum));
    lazy = 0;
  }
  node(int val) {
    sum[0] = val;
    for (int x = 1; x < period; x++) sum[x] = cube(sum[x - 1]);
    lazy = 0;
  }
};
node temp, broken;
node merge(node l, node r) {
  for (int i = 0; i < period; i++) temp.sum[i] = (l.sum[i] + r.sum[i]) % mod;
  temp.lazy = 0;
  return temp;
}
struct segment_tree {
  node tr[4 * MAXN];
  void push(int l, int r, int idx) {
    if (tr[idx].lazy) {
      for (int i = 0; i < period; i++) temp.sum[i] = tr[idx].sum[i];
      for (int i = 0; i < period; i++)
        tr[idx].sum[i] = temp.sum[(i + tr[idx].lazy) % period];
      if (l != r) {
        tr[2 * idx + 1].lazy += tr[idx].lazy;
        tr[2 * idx + 2].lazy += tr[idx].lazy;
        tr[2 * idx + 1].lazy %= period;
        tr[2 * idx + 2].lazy %= period;
      }
      tr[idx].lazy = 0;
    }
  }
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = node(a[l]);
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  void update(int qL, int qR, int val, int l, int r, int idx) {
    push(l, r, idx);
    if (qL > r || l > qR) return;
    if (qL <= l && r <= qR) {
      tr[idx].lazy += val;
      tr[idx].lazy %= period;
      push(l, r, idx);
      return;
    }
    int mid = (l + r) >> 1;
    update(qL, qR, val, l, mid, 2 * idx + 1);
    update(qL, qR, val, mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  node query(int qL, int qR, int l, int r, int idx) {
    push(l, r, idx);
    if (l > qR || r < qL) return broken;
    if (qL <= l && r <= qR) return tr[idx];
    int mid = (l + r) >> 1;
    return merge(query(qL, qR, l, mid, 2 * idx + 1),
                 query(qL, qR, mid + 1, r, 2 * idx + 2));
  }
};
void read() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
}
segment_tree t;
void solve() {
  t.init(0, n - 1, 0);
  cin >> m;
  for (int i = 0; i < m; i++) {
    int type, l, r;
    cin >> type >> l >> r;
    if (type == 1)
      cout << t.query(l - 1, r - 1, 0, n - 1, 0).sum[0] << '\n';
    else
      t.update(l - 1, r - 1, 1, 0, n - 1, 0);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}
