package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

const MOD = 95542721

type Node struct {
	sums [48]int
	lazy int
}

var tree []Node
var a []int
var data []byte
var pos int

func nextInt() int {
	for pos < len(data) && data[pos] <= ' ' {
		pos++
	}
	if pos >= len(data) {
		return 0
	}
	res := 0
	for pos < len(data) && data[pos] > ' ' {
		res = res*10 + int(data[pos]-'0')
		pos++
	}
	return res
}

func pushUp(u int) {
	for i := 0; i < 48; i++ {
		tree[u].sums[i] = tree[2*u].sums[i] + tree[2*u+1].sums[i]
		if tree[u].sums[i] >= MOD {
			tree[u].sums[i] -= MOD
		}
	}
}

func shift(u int, k int) {
	if k == 0 {
		return
	}
	var next [48]int
	for i := 0; i < 48; i++ {
		idx := i + k
		if idx >= 48 {
			idx -= 48
		}
		next[i] = tree[u].sums[idx]
	}
	tree[u].sums = next
	tree[u].lazy += k
	if tree[u].lazy >= 48 {
		tree[u].lazy -= 48
	}
}

func pushDown(u int) {
	if tree[u].lazy > 0 {
		shift(2*u, tree[u].lazy)
		shift(2*u+1, tree[u].lazy)
		tree[u].lazy = 0
	}
}

func build(u, l, r int) {
	if l == r {
		val := a[l] % MOD
		tree[u].sums[0] = val
		for i := 1; i < 48; i++ {
			val = int(int64(val) * int64(val) % MOD * int64(val) % MOD)
			tree[u].sums[i] = val
		}
		return
	}
	mid := (l + r) / 2
	build(2*u, l, mid)
	build(2*u+1, mid+1, r)
	pushUp(u)
}

func update(u, l, r, ql, qr int) {
	if ql <= l && r <= qr {
		shift(u, 1)
		return
	}
	pushDown(u)
	mid := (l + r) / 2
	if ql <= mid {
		update(2*u, l, mid, ql, qr)
	}
	if qr > mid {
		update(2*u+1, mid+1, r, ql, qr)
	}
	pushUp(u)
}

func query(u, l, r, ql, qr int) int {
	if ql <= l && r <= qr {
		return tree[u].sums[0]
	}
	pushDown(u)
	mid := (l + r) / 2
	res := 0
	if ql <= mid {
		res += query(2*u, l, mid, ql, qr)
	}
	if qr > mid {
		res += query(2*u+1, mid+1, r, ql, qr)
	}
	if res >= MOD {
		res -= MOD
	}
	return res
}

func main() {
	data, _ = io.ReadAll(os.Stdin)

	n := nextInt()
	if n == 0 {
		return
	}

	a = make([]int, n+1)
	for i := 1; i <= n; i++ {
		a[i] = nextInt()
	}

	tree = make([]Node, 4*n+1)
	build(1, 1, n)

	q := nextInt()
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < q; i++ {
		t := nextInt()
		l := nextInt()
		r := nextInt()

		if t == 1 {
			ans := query(1, 1, n, l, r)
			fmt.Fprintln(out, ans)
		} else if t == 2 {
			update(1, 1, n, l, r)
		}
	}
}