Subset of Master Shifu

shefin Criterion 2021 Round 10
Limits 3s, 512 MB

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. Taking index $\{1\}$. Subset = $\{20\}$. Sum = $20$.
  2. Taking indexes $\{1, 2\}$. Subset = $\{20, 10\}$. Sum = $30$.
  3. Taking index $\{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).

Input

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

Output

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.

Sample

InputOutput
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,
Subsets in lexicographically ascending order will be:

  1. Taking index $\{1\}$. Subset = $\{81\}$. Sum = $81$.
  2. Taking indexes $\{1,2\}$. Subset = $\{81,93\}$. Sum = $174$.
  3. Taking indexes $\{1,2,3\}$. Subset = $\{81,93,93\}$. Sum = $267$.
  4. Taking indexes $\{1,3\}$. Subset = $\{81,93\}$. Sum = $174$.
  5. Taking index $\{2\}$. Subset = $\{93\}$. Sum = $93$.
  6. Taking indexes $\{2,3\}$. Subset = $\{93,93\}$. Sum = $186$.
  7. Taking index $\{3\}$. Subset = $\{93\}$. Sum = $93$.

So, the $B$ array is $\{81, 174, 267, 174, 93, 186, 93\}$.
Sorted elements in $[4,7]$ indexes will be $\{93, 93, 174, 186\}$. So, the $2^{nd}$ element will be $93$.
Sorted elements in $[1,5]$ indexes will be $\{81, 93, 174, 174, 267\}$. So, the $5^{th}$ element will be $267$.

In the third query, we have to update the value of $A_3 = 5$. After the update, the $A$ array will be $\{81,93,5\}$.


Submit

Login to submit.

Statistics

67% Solution Ratio
sansaquaEarliest, Feb '21
ShadowMeFastest, 1.4s
ShadowMeLightest, 5.1 MB
ShadowMeShortest, 3823B
Toph uses cookies. By continuing you agree to our Cookie Policy.