#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long inf = 1e9 + 6;
const long long MOD = 1e9 + 7;
const long long mod = 95542721;
const int MX = 1e5 + 5;
const int LG = 25;
template <typename t>
void fff(const char* x, t&& val1) {
  cout << x << " : " << val1 << "\n";
}
template <typename t1, typename... t2>
void fff(const char* x, t1&& val1, t2&&... val2) {
  const char* xd = strchr(x + 1, ',');
  cout.write(x, xd - x) << " : " << val1 << " | ";
  fff(xd + 1, val2...);
}
static inline void read(long long& result) {
  bool minus = false;
  char ch;
  ch = getchar();
  while (true) {
    if (ch == '-') break;
    if (ch >= '0' and ch <= '9') break;
    ch = getchar();
  }
  (ch == '-') ? minus = true : result = ch - '0';
  while (true) {
    ch = getchar();
    if (ch < '0' or ch > '9') break;
    result = (result << 3) + (result << 1) + (ch - '0');
  }
  if (minus) result = -result;
}
struct ga {
  long long t[48];
} tree[4 * MX];
long long lazy[4 * MX], a[MX];
inline long long pw3(long long a) { return ((a * a) % mod * a) % mod; }
inline ga op(ga a, ga b) {
  ga aux;
  for (int i = 0; i < 48; i++) aux.t[i] = (a.t[i] + b.t[i]) % mod;
  return aux;
}
inline void updpro(long long val, long long v, long long tl, long long tr) {
  if (val != 0) {
    vector<long long> v1;
    for (int i = 0; i < 48; i++) v1.push_back(tree[v].t[(i + val) % 48]);
    for (int i = 0; i < 48; i++) tree[v].t[i] = v1[i];
    lazy[v] = (lazy[v] + val) % 48;
  }
}
inline void pro(long long v, long long l, long long r) {
  long long mid = (l + r) >> 1;
  updpro(lazy[v], 2 * v, l, mid);
  updpro(lazy[v], 2 * v + 1, mid + 1, r);
  lazy[v] = 0;
}
inline void build(long long v, long long tl, long long tr) {
  if (tl == tr) {
    tree[v].t[0] = a[tl];
    for (int i = 1; i < 48; i++) {
      tree[v].t[i] = pw3(tree[v].t[i - 1]);
    }
  } else {
    long long tm = (tl + tr) >> 1;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v] = op(tree[2 * v], tree[2 * v + 1]);
  }
}
inline void update(long long v, long long tl, long long tr, long long l,
                   long long r, long long val) {
  if (l > tr || tl > r) return;
  if (l <= tl && tr <= r) {
    updpro(val, v, tl, tr);
  } else {
    pro(v, tl, tr);
    long long tm = (tl + tr) >> 1;
    update(2 * v, tl, tm, l, r, val);
    update(2 * v + 1, tm + 1, tr, l, r, val);
    tree[v] = op(tree[2 * v], tree[2 * v + 1]);
  }
}
inline long long query(long long v, long long tl, long long tr, long long l,
                       long long r) {
  if (l > tr || tl > r) return 0;
  if (l <= tl && tr <= r) {
    return tree[v].t[0];
  } else {
    pro(v, tl, tr);
    long long tm = (tl + tr) >> 1;
    return (query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r)) %
           mod;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  read(n);
  for (int i = 0; i < n; i++) read(a[i]);
  build(1, 0, n - 1);
  long long q;
  read(q);
  while (q--) {
    long long ty, a, b;
    read(ty);
    read(a);
    read(b);
    a--;
    b--;
    if (ty == 1) {
      cout << query(1, 0, n - 1, a, b) << endl;
    } else {
      update(1, 0, n - 1, a, b, 1);
    }
  }
}
