#include <bits/stdc++.h>
using namespace std;
const int NMax = 101000, INF = 95542721;
struct node {
  int first[50], cur, lazy;
} T[NMax * 4];
int N, Q, A[NMax];
void build(int l, int r, int p) {
  if (l == r) {
    int now = A[l] % INF;
    T[p].first[0] = now;
    for (int i = 1; i < 48; i++) {
      long long tmp = ((long long)now * now) % INF;
      tmp = (tmp * now) % INF;
      now = tmp;
      T[p].first[i] = now;
    }
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, p * 2);
  build(mid + 1, r, p * 2 + 1);
  for (int i = 0; i < 48; i++)
    T[p].first[i] = (T[p * 2].first[i] + T[p * 2 + 1].first[i]) % INF;
}
int ask(int a, int b, int l, int r, int p) {
  if (a == l && b == r) {
    return T[p].first[T[p].cur];
  }
  if (T[p].lazy) {
    T[p * 2].lazy += T[p].lazy;
    T[p * 2 + 1].lazy += T[p].lazy;
    T[p * 2].cur = (T[p * 2].cur + T[p].lazy) % 48;
    T[p * 2 + 1].cur = (T[p * 2 + 1].cur + T[p].lazy) % 48;
    T[p].lazy = 0;
  }
  int mid = (a + b) >> 1;
  int ret;
  if (mid >= r)
    ret = ask(a, mid, l, r, p * 2);
  else if (mid < l)
    ret = ask(mid + 1, b, l, r, p * 2 + 1);
  else
    ret =
        (ask(a, mid, l, mid, p * 2) + ask(mid + 1, b, mid + 1, r, p * 2 + 1)) %
        INF;
  int p0 = T[p * 2].cur, p1 = T[p * 2 + 1].cur;
  for (int i = 0; i < 48; i++) {
    T[p].first[i] = (T[p * 2].first[p0] + T[p * 2 + 1].first[p1]) % INF;
    p0 = (p0 + 1) % 48;
    p1 = (p1 + 1) % 48;
  }
  T[p].cur = 0;
  return ret;
}
void change(int a, int b, int l, int r, int p) {
  if (a == l && b == r) {
    T[p].lazy++;
    T[p].cur = (T[p].cur + 1) % 48;
    return;
  }
  if (T[p].lazy) {
    T[p * 2].lazy += T[p].lazy;
    T[p * 2 + 1].lazy += T[p].lazy;
    T[p * 2].cur = (T[p * 2].cur + T[p].lazy) % 48;
    T[p * 2 + 1].cur = (T[p * 2 + 1].cur + T[p].lazy) % 48;
    T[p].lazy = 0;
  }
  int mid = (a + b) >> 1;
  if (mid >= r)
    change(a, mid, l, r, p * 2);
  else if (mid < l)
    change(mid + 1, b, l, r, p * 2 + 1);
  else {
    change(a, mid, l, mid, p * 2);
    change(mid + 1, b, mid + 1, r, p * 2 + 1);
  }
  int p0 = T[p * 2].cur, p1 = T[p * 2 + 1].cur;
  for (int i = 0; i < 48; i++) {
    T[p].first[i] = (T[p * 2].first[p0] + T[p * 2 + 1].first[p1]) % INF;
    p0 = (p0 + 1) % 48;
    p1 = (p1 + 1) % 48;
  }
  T[p].cur = 0;
}
int M;
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%d", A + i);
  build(1, N, 1);
  scanf("%d", &M);
  for (int i = 1; i <= M; i++) {
    int t, first, second;
    scanf("%d%d%d", &t, &first, &second);
    if (t == 1) {
      printf("%d\n", ask(1, N, first, second, 1));
    } else {
      change(1, N, first, second, 1);
    }
  }
  return 0;
}
