#include <bits/stdc++.h>
int a[100000 + 5], n;
void Init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  return;
}
int val[100000 * 4 + 5][48 + 5], pos[100000 * 4 + 5];
inline void Update(int root) {
  for (int i = 0; i < 48; i++)
    val[root][i] = (val[root << 1][(i + pos[root << 1]) % 48] +
                    val[root << 1 | 1][(i + pos[root << 1 | 1]) % 48]) %
                   95542721;
  return;
}
inline void Push(int root) {
  pos[root << 1] = (pos[root << 1] + pos[root]) % 48;
  pos[root << 1 | 1] = (pos[root << 1 | 1] + pos[root]) % 48;
  pos[root] = 0;
  return;
}
inline void Insert(int root, int L, int R) {
  if (L == R) {
    long long t = a[L];
    for (int i = 0; i < 48; i++) {
      val[root][i] = t;
      t = t * t % 95542721 * t % 95542721;
    }
    return;
  }
  int mid = (L + R) >> 1;
  Insert(root << 1, L, mid);
  Insert(root << 1 | 1, mid + 1, R);
  Update(root);
  return;
}
inline void Modify(int root, int L, int R, int s, int t) {
  if (R < s || t < L) return;
  if (s <= L && R <= t) {
    pos[root] = (pos[root] + 1) % 48;
    return;
  }
  Push(root);
  int mid = (L + R) >> 1;
  Modify(root << 1, L, mid, s, t);
  Modify(root << 1 | 1, mid + 1, R, s, t);
  Update(root);
  return;
}
int tmp[48 + 5];
inline int Query(int root, int L, int R, int s, int t) {
  if (R < s || t < L) return 0;
  if (s <= L && R <= t) return val[root][pos[root]];
  for (int i = 0; i < 48; i++) tmp[i] = val[root][i];
  for (int i = 0; i < 48; i++) val[root][i] = tmp[(i + pos[root]) % 48];
  Push(root);
  int mid = (L + R) >> 1;
  return (Query(root << 1, L, mid, s, t) +
          Query(root << 1 | 1, mid + 1, R, s, t)) %
         95542721;
}
void Segment_Tree() {
  Insert(1, 1, n);
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    char opt = getchar();
    while (opt != '1' && opt != '2') opt = getchar();
    int s, t;
    scanf("%d %d", &s, &t);
    if (opt == '1')
      printf("%d\n", Query(1, 1, n, s, t));
    else
      Modify(1, 1, n, s, t);
  }
  return;
}
int main() {
  Init();
  Segment_Tree();
  getchar();
  getchar();
  return 0;
}
