While learning Computational Geometry, Tiny is simultaneously learning a useful data structure called segment tree or interval tree. He has scarcely grasped it when comes out a strange problem:

Given an integer sequence $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$. You should run $*q*$ queries of two types:

1. Given two integers $*l*$ and $*r*$ ($1 ≤ *l* ≤ *r* ≤ *n*$), ask the sum of all elements in the sequence $*a*_{*l*}, *a*_{*l* + 1}, ..., *a*_{*r*}$.
2. Given two integers $*l*$ and $*r*$ ($1 ≤ *l* ≤ *r* ≤ *n*$), let each element $*x*$ in the sequence $*a*_{*l*}, *a*_{*l* + 1}, ..., *a*_{*r*}$ becomes $*x*^{3}$. In other words, apply an assignments $*a*_{*l*} = *a*_{*l*}^{3}, *a*_{*l* + 1} = *a*_{*l* + 1}^{3}, ..., *a*_{*r*} = *a*_{*r*}^{3}$.

For every query of type 1, output the answer to it.

Tiny himself surely cannot work it out, so he asks you for help. In addition, Tiny is a prime lover. He tells you that because the answer may be too huge, you should only output it modulo $95542721$ (this number is a prime number).

Input

The first line contains an integer $*n*$ ($1 ≤ *n* ≤ 10^{5}$), representing the length of the sequence. The second line contains $*n*$ space-separated integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($0 ≤ *a*_{*i*} ≤ 10^{9}$).

The third line contains an integer $*q*$ ($1 ≤ *q* ≤ 10^{5}$), representing the number of queries. Then follow $*q*$ lines. Each line contains three integers $*t*_{*i*}$ ($1 ≤ *t*_{*i*} ≤ 2$), $*l*_{*i*}$, $*r*_{*i*}$ ($1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*$), where $*t*_{*i*}$ stands for the type of the query while $*l*_{*i*}$ and $*r*_{*i*}$ is the parameters of the query, correspondingly.

Output

For each 1-type query, print the answer to it per line.

You should notice that each printed number should be non-negative and less than $95542721$.