B'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 a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an. You should run q queries of two types: 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). The first line contains an integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105), representing the length of the sequence. The second line contains n space-separated integers a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an (0 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109). The third line contains an integer q (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89q xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105), representing the number of queries. Then follow q lines. Each line contains three integers ti (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ti xe2 x80 x89 xe2 x89 xa4 xe2 x80 x892), li, ri (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89li xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ri xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n), where ti stands for the type of the query while li and ri is the parameters of the query, correspondingly. 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.'...