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₁,a₂,...,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³. In other words, apply an assignments a_l=a_l³,a_l+1=a_l+1³,...,a_r=a_r³.

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).