While traveling in dreamland, you've met the highly skilled master of kung fu, "Master Shifu". As you are in dreamland, you've astonishingly found out that master Shifu also knows programming and problem-solving. He is working on a problem now. The problem is described below:
Master Shifu has an array of size . He writes down all possible subsets of the array in lexicographically ascending order. He doesn't write the empty subset. After that, he creates another array of size by taking the sum of each subset maintaining the order of the subsets.
A subset of the array is a tuple that can be obtained from by removing some (possibly all) elements of it.
Master Shifu tells a subset is lexicographically smaller than another subset if they meet the following condition:
He generates two ascendingly sorted sequences and . contains the indexes of the array that are present in the subset and contains the indexes of the array that are present in the subset . Subset is lexicographically smaller than subset if is a prefix of or there exists , such that and for all it is satisfied that .
For example, if an array is , all possible subsets of it in lexicographically ascending order will be:
So, the array will be . Note that the lexicographical ordering of the subsets depends on the indexes of the array that are present in the subsets. It doesn't depend on the elements of the subsets at all.
He tells you to perform queries:
:For this type of queries, you have to set , where is an index of the array (1-based indexing).
:For this type of queries, You have to generate the array at first. After that, you have to print the element in the range of indexes of array if you sort all elements of indexes ascendingly (1-based indexing).
The first line contains two integers and , the size of the array and the number of queries respectively.
The next line contains space separated integers , the elements of the array .
The next lines contains two types of queries:
For each of the second type of queries, print the value of the element in the range of indexes in a line as described in the statement.
3 5 81 93 93 2 4 7 2 2 1 5 5 1 3 5 2 1 5 5 2 4 7 2
93 267 179 86
For the first and second queries,
So, the array is .
In the third query, we have to update the value of . After the update, the array will be .
Login to submit
The key factor of the problem is, only the first 666 elements of the array will be updated at most. ...