CF311D Interval Cubing

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

The first line contains an integer $ n $ ( $ 1

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