#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000007;
const long long linf = 1000000000000000000LL;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T k) {
  return k >= 0 ? k : -k;
}
template <class T>
T sqr(T n) {
  return n * n;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  return (a % b + b) % b;
}
template <class T>
T addmod(T a, T b, T c) {
  return (T)((long long)(a + b) % c);
}
template <class T>
T mulmod(T a, T b, T c) {
  return (T)((long long)a * b % c);
}
template <class T>
T powmod(T a, T b, T c) {
  return (T)(b ? sqr((long long)powmod(a, b >> 1, c)) % c * (b & 1 ? a : 1) % c
               : 1);
}
template <class T>
void maxe(T &a, T b) {
  a = max(a, b);
}
template <class T>
void mine(T &a, T b) {
  a = min(a, b);
}
template <class T>
void mode(T &a, T b) {
  a = mod(a, b);
}
template <class T>
void addmode(T &a, T b, T c) {
  a = addmod(a, b, c);
}
template <class T>
void mulmode(T &a, T b, T c) {
  a = mulmod(a, b, c);
}
template <class T>
void powmode(T &a, T b, T c) {
  a = powmod(a, b, c);
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 111111;
int test;
int n, m, k, ans;
int a[N], tmp[55];
int l, r;
const int md = 95542721;
struct Seg {
  int left, right;
  int s[55], lazy;
} seg[N << 2];
int cube(int a) { return (long long)a * a % md * a % md; }
void push_up(int node) {
  for (int i = 0; i < 48; i++)
    seg[node].s[i] = (seg[node << 1].s[i] + seg[node << 1 | 1].s[i]) % md;
}
void modify(int node, int k) {
  seg[node].lazy += k;
  for (int i = 0; i < 48; i++) tmp[i] = seg[node].s[(i + k) % 48];
  for (int i = 0; i < 48; i++) seg[node].s[i] = tmp[i];
}
void push_down(int node) {
  if (seg[node].lazy) {
    modify(node << 1, seg[node].lazy);
    modify(node << 1 | 1, seg[node].lazy);
    seg[node].lazy = 0;
  }
}
void build(int node, int l, int r) {
  seg[node].left = l;
  seg[node].right = r;
  seg[node].lazy = 0;
  if (l == r) {
    seg[node].s[0] = a[l] % md;
    for (int i = 1; i < 48; i++) seg[node].s[i] = cube(seg[node].s[i - 1]);
    return;
  }
  int mid = (l + r) >> 1;
  build(node << 1, l, mid);
  build(node << 1 | 1, mid + 1, r);
  push_up(node);
}
void update(int node, int l, int r) {
  if (seg[node].left == l && seg[node].right == r) {
    modify(node, 1);
    return;
  }
  push_down(node);
  int mid = (seg[node].left + seg[node].right) >> 1;
  if (r <= mid)
    update(node << 1, l, r);
  else {
    if (l > mid)
      update(node << 1 | 1, l, r);
    else {
      update(node << 1, l, mid);
      update(node << 1 | 1, mid + 1, r);
    }
  }
  push_up(node);
}
int query(int node, int l, int r) {
  if (seg[node].left == l && seg[node].right == r) return seg[node].s[0];
  push_down(node);
  int mid = (seg[node].left + seg[node].right) >> 1;
  if (r <= mid)
    return query(node << 1, l, r);
  else {
    if (l > mid)
      return query(node << 1 | 1, l, r);
    else
      return (query(node << 1, l, mid) + query(node << 1 | 1, mid + 1, r)) % md;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1)
      printf("%d\n", query(1, l, r));
    else
      update(1, l, r);
  }
  return 0;
}
