#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
A cvt(B x) {
  stringstream ss;
  ss << x;
  A y;
  ss >> y;
  return y;
}
int n, q;
int a[100000];
struct node {
  int s[48];
  int l, r, n;
  int todo;
};
node t[300000];
void join(int x) {
  int xl = 2 * x, xr = 2 * x + 1;
  for (int i = 0; i < (int)(48); i++) {
    t[x].s[i] = (t[xl].s[i] + t[xr].s[i]) % 95542721;
  }
}
void build(int x, int l, int r) {
  t[x].l = l;
  t[x].r = r;
  t[x].n = r - l;
  if (r - l == 1) {
    t[x].s[0] = a[l];
    for (int i = (1); i <= (47); i++) {
      t[x].s[i] = 1;
      for (int j = 0; j < (int)(3); j++) {
        t[x].s[i] = ((long long)t[x].s[i] * t[x].s[i - 1]) % 95542721;
      }
    }
  } else {
    int m = (l + r) / 2, xl = 2 * x, xr = 2 * x + 1;
    build(xl, l, m);
    build(xr, m, r);
    join(x);
  }
}
void push(int x) {
  if (t[x].todo > 0) {
    rotate(t[x].s, t[x].s + t[x].todo % 48, t[x].s + 48);
    if (t[x].n > 1) {
      t[2 * x].todo += t[x].todo;
      t[2 * x + 1].todo += t[x].todo;
    }
    t[x].todo = 0;
  }
}
int query(int x, int l, int r) {
  push(x);
  if (r <= t[x].l || t[x].r <= l) {
    return 0;
  } else if (l <= t[x].l && t[x].r <= r) {
    return t[x].s[0];
  } else {
    return (query(2 * x, l, r) + query(2 * x + 1, l, r)) % 95542721;
  }
}
void update(int x, int l, int r) {
  push(x);
  if (r <= t[x].l || t[x].r <= l) {
    return;
  } else if (l <= t[x].l && t[x].r <= r) {
    t[x].todo++;
    push(x);
  } else {
    update(2 * x, l, r);
    update(2 * x + 1, l, r);
    join(x);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); i++) scanf("%d", &a[i]);
  build(1, 0, n);
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); i++) {
    int qt, l, r;
    scanf("%d %d %d", &qt, &l, &r);
    l--;
    r--;
    if (qt == 1) {
      printf("%d\n", query(1, l, r + 1));
    } else {
      update(1, l, r + 1);
    }
  }
  return 0;
}
