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 $A$
of size $N$
. He writes down all possible subsets of the array $A$
in lexicographically ascending order. He doesn't write the empty subset. After that, he creates another array $B$
of size $2^N-1$
by taking the sum of each subset maintaining the order of the subsets.
A subset of the array $A$
is a tuple that can be obtained from $A$
by removing some (possibly all) elements of it.
Master Shifu tells a subset $S_1$
is lexicographically smaller than another subset $S_2$
if they meet the following condition:
He generates two ascendingly sorted sequences $x$
and $y$
. $x$
contains the indexes of the array $A$
that are present in the subset $S_1$
and $y$
contains the indexes of the array $A$
that are present in the subset $S_2$
. Subset $S_1$
is lexicographically smaller than subset $S_2$
if $x$
is a prefix of $y$
or there exists $i$
, such that $x_i < y_i$
and for all $j < i$
it is satisfied that $x_j = y_j$
.
For example, if an array is $\{20,10\}$
, all possible subsets of it in lexicographically ascending order will be:
$\{1\}$
. Subset = $\{20\}$
. Sum = $20$
.$\{1, 2\}$
. Subset = $\{20, 10\}$
. Sum = $30$
.$\{2\}$
. Subset = $\{10\}$
. Sum = $10$
.So, the $B$
array will be $\{20, 30, 10\}$
. Note that the lexicographical ordering of the subsets depends on the indexes of the array $A$
that are present in the subsets. It doesn't depend on the elements of the subsets at all.
He tells you to perform $Q$
queries:
$1\space P\space C$
:For this type of queries, you have to set $A_P = C$
, where $P$
is an index of the array $A$
(1-based indexing).
$2\space L\space R\space K$
:For this type of queries, You have to generate the $B$
array at first. After that, you have to print the $K^{th}$
element in the range of $[L,R]$
indexes of $B$
array if you sort all elements of $[L,R]$
indexes ascendingly (1-based indexing).
The first line contains two integers $N$
and $Q$
, the size of the array $A$
and the number of queries respectively.
The next line contains $N$
space separated integers $A_i$
, the elements of the array $A$
.
The next $Q$
lines contains two types of queries:
$1\space P\space C$
$2\space L\space R\space K$
Constraints:$1\leq N \leq 20$
$1\leq Q\leq10^4$
$1\leq A_i, C\leq10^{9}$
$1\leq P\leq min(N,6)$
$1\leq L\leq R < 2^N$
$1\leq K\leq (R-L+1)$
For each of the second type of queries, print the value of the $K^{th}$
element in the range of $[L,R]$
indexes in a line as described in the statement.
Input | Output |
---|---|
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 |
Notes: For the first and second queries,
So, the In the third query, we have to update the value of |