Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subset of Master Shifu

By shefin · 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 AA of size NN. He writes down all possible subsets of the array AA in lexicographically ascending order. He doesn't write the empty subset. After that, he creates another array BB of size 2N12^N-1 by taking the sum of each subset maintaining the order of the subsets.

A subset of the array AA is a tuple that can be obtained from AA by removing some (possibly all) elements of it.

Master Shifu tells a subset S1S_1 is lexicographically smaller than another subset S2S_2 if they meet the following condition:
He generates two ascendingly sorted sequences xx and yy. xx contains the indexes of the array AA that are present in the subset S1S_1 and yy contains the indexes of the array AA that are present in the subset S2S_2. Subset S1S_1 is lexicographically smaller than subset S2S_2 if xx is a prefix of yy or there exists ii, such that xi<yix_i < y_i and for all j<ij < i it is satisfied that xj=yjx_j = y_j.

For example, if an array is {20,10}\{20,10\}, all possible subsets of it in lexicographically ascending order will be:

  1. Taking index {1}\{1\}. Subset = {20}\{20\}. Sum = 2020.
  2. Taking indexes {1,2}\{1, 2\}. Subset = {20,10}\{20, 10\}. Sum = 3030.
  3. Taking index {2}\{2\}. Subset = {10}\{10\}. Sum = 1010.

So, the BB array will be {20,30,10}\{20, 30, 10\}. Note that the lexicographical ordering of the subsets depends on the indexes of the array AA that are present in the subsets. It doesn't depend on the elements of the subsets at all.

He tells you to perform QQ queries:

  • 1 P C1\space P\space C:For this type of queries, you have to set AP=CA_P = C, where PP is an index of the array AA (1-based indexing).

  • 2 L R K2\space L\space R\space K:For this type of queries, You have to generate the BB array at first. After that, you have to print the KthK^{th} element in the range of [L,R][L,R] indexes of BB array if you sort all elements of [L,R][L,R] indexes ascendingly (1-based indexing).

Input

The first line contains two integers NN and QQ, the size of the array AA and the number of queries respectively.
The next line contains NN space separated integers AiA_i, the elements of the array AA.

The next QQ lines contains two types of queries:

  • 1 P C1\space P\space C
  • 2 L R K2\space L\space R\space K

Constraints:
1N201\leq N \leq 20
1Q1041\leq Q\leq10^4
1Ai,C1091\leq A_i, C\leq10^{9}
1Pmin(N,6)1\leq P\leq min(N,6)
1LR<2N1\leq L\leq R < 2^N
1K(RL+1)1\leq K\leq (R-L+1)

Output

For each of the second type of queries, print the value of the KthK^{th} element in the range of [L,R][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}\{1\}. Subset = {81}\{81\}. Sum = 8181.
  2. Taking indexes {1,2}\{1,2\}. Subset = {81,93}\{81,93\}. Sum = 174174.
  3. Taking indexes {1,2,3}\{1,2,3\}. Subset = {81,93,93}\{81,93,93\}. Sum = 267267.
  4. Taking indexes {1,3}\{1,3\}. Subset = {81,93}\{81,93\}. Sum = 174174.
  5. Taking index {2}\{2\}. Subset = {93}\{93\}. Sum = 9393.
  6. Taking indexes {2,3}\{2,3\}. Subset = {93,93}\{93,93\}. Sum = 186186.
  7. Taking index {3}\{3\}. Subset = {93}\{93\}. Sum = 9393.

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

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


    Discussion

    Statistics


    67% Solution Ratio

    sansaquaEarliest, 6M ago

    ShadowMeFastest, 1.4s

    ShadowMeLightest, 5.1 MB

    ShadowMeShortest, 3823B

    Submit

    Login to submit

    Editorial

    The key factor of the problem is, only the first 666 elements of the array will be updated at most. ...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.