Liones的寶石 3

題目敘述

經由上兩次的協助後，$Liones$的家中依然有許多閃閃發亮的寶石，一個接一個的直線排列在桌子上，每天$Liones$要出門為自己打扮妝點的時候，就會順手的從桌上抓取一個寶石來配戴在自己身上，凸顯自己的身分地位。在$Liones$的概念中是以$0$開始記數的，因此最左邊的寶石稱之為第$0$個寶石，最大的寶石會被稱為第$0$大的寶石，但是因為$Liones$不喜歡不是最大的東西，要她選擇第$K$大的寶石，實際上她會拿第$K\&1$大的寶石，符號$\&$等同於C++的位元$\&$運算。而每一個寶石$Liones$的造型都有不同的加成效果，稱之為美感分數，比如說亮眼的紅寶石因為十分的耀眼，有100分的分數，而綠寶石與$Liones$平時的打扮十分不搭，穿上後會獲得$-87$的分數，大量扣分。因此。如果沒有穿著寶石的話則$Liones$的美感分數是$-1$分。

不過$Liones$平時十分懶惰，爸爸為了幫她仔細妝點打扮，爸爸每一天會要$Liones$拿一個擺放在指定區間第$K$大的寶石直接穿在身上，如果沒有就不拿，此外$Liones$的爸爸為了讓$Liones$有更多選擇，有時會隨機的更換在桌上的寶石，讓每一天$Liones$的美感分數都不太一樣，因此$Liones$很好奇自己每天都這樣隨爸爸命令抓取寶石下，自己的美感分數會是多少，身為僕人的你可以幫忙計算嗎？

輸入說明

測資一開始有一個數字$N$，表示桌上有多少寶石，接下來下一行有$N$個整數$a_0,a_1,\cdots a_{N-1}$，依序表示桌上寶石的美感分數。接下來有一個整數$Q$，表示有$Q$個動作。

接下來$Q$行動作有兩種格式

0 L v，表示爸爸把第$L$個寶石更換成美感分數$v$分的寶石。
1 L R K，表示爸爸那一天要$Liones$要從$[L,R]$(含頭尾)之間抓取分數第$K$大的寶石。
$0 \leq Q \leq 10^5$
$0 \leq L \leq R < N \leq 10^5$
$ 0 \leq K < R-L+1$
$0 \leq a_i \leq 10^5$

輸出說明

對於每一個抓取寶石的動作輸出一行，為$Liones$該次可獲得的美感分數。

範例輸入

6
1 2 3 4 5 6
5
1 0 5 0
1 0 5 1
0 5 1
1 0 5 0
1 0 5 1

範例輸出

提示

Tip:測資很大、線段樹。

Judge Setting

run-time limit: 100 ms
memory limit: 6553600 byte
測資數量: 0