#include <bits/stdc++.h>
using namespace std;
const long long mod = 95542721LL;
const int maxN = 101000;
long long sum[4 * maxN];
long long add[4 * maxN];
long long val[4 * maxN][48];
long long a[maxN];
int n, m;
void getmod(long long& value) {
  while (value >= mod) {
    value -= mod;
  }
}
void build(int v, int cl, int cr) {
  if (cl == cr) {
    val[v][0] = a[cl];
    for (int i = 1; i < 48; ++i) {
      val[v][i] = ((val[v][i - 1] * val[v][i - 1]) % mod * val[v][i - 1]) % mod;
    }
    sum[v] = val[v][0];
    return;
  }
  int mid = (cl + cr) / 2;
  build(2 * v, cl, mid);
  build(2 * v + 1, mid + 1, cr);
  for (int i = 0; i < 48; ++i) {
    val[v][i] = val[2 * v][i] + val[2 * v + 1][i];
    getmod(val[v][i]);
  }
  sum[v] = sum[2 * v] + sum[2 * v + 1];
  getmod(sum[v]);
}
void update(int v, int cl, int cr, int step) {
  add[v] = (add[v] + step) % 48;
  step = step % 48;
  long long bufval[48];
  for (int i = 0; i < 48; ++i) {
    int x = (i + step) % 48;
    bufval[i] = val[v][x];
  }
  for (int i = 0; i < 48; ++i) {
    val[v][i] = bufval[i];
  }
  sum[v] = val[v][0];
}
void push(int v, int cl, int cr) {
  long long buf = add[v];
  add[v] = 0;
  int mid = (cl + cr) / 2;
  update(2 * v, cl, mid, buf);
  update(2 * v + 1, mid + 1, cr, buf);
}
void update(int v, int cl, int cr, int tl, int tr) {
  if (cl == tl && cr == tr) {
    update(v, cl, cr, 1);
    return;
  }
  push(v, cl, cr);
  int mid = (cl + cr) / 2;
  if (tr <= mid) {
    update(2 * v, cl, mid, tl, tr);
  } else if (tl > mid) {
    update(2 * v + 1, mid + 1, cr, tl, tr);
  } else {
    update(2 * v, cl, mid, tl, mid);
    update(2 * v + 1, mid + 1, cr, mid + 1, tr);
  }
  for (int i = 0; i < 48; ++i) {
    val[v][i] = (val[2 * v][i] + val[2 * v + 1][i]);
    getmod(val[v][i]);
  }
  sum[v] = (sum[2 * v] + sum[2 * v + 1]);
  getmod(sum[v]);
}
long long get(int v, int cl, int cr, int tl, int tr) {
  if (cl == tl && cr == tr) {
    return sum[v];
  }
  push(v, cl, cr);
  int mid = (cl + cr) / 2;
  if (tr <= mid) {
    return get(2 * v, cl, mid, tl, tr);
  }
  if (tl > mid) {
    return get(2 * v + 1, mid + 1, cr, tl, tr);
  }
  long long ret =
      (get(2 * v, cl, mid, tl, mid) + get(2 * v + 1, mid + 1, cr, mid + 1, tr));
  getmod(ret);
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    x %= mod;
    a[i] = x;
  }
  build(1, 1, n);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    int t, x, y;
    scanf("%d%d%d", &t, &x, &y);
    if (t == 2) {
      update(1, 1, n, x, y);
    } else {
      printf("%I64d\n", get(1, 1, n, x, y));
    }
  }
  return 0;
}
