帝國的風雨飄搖

在遙遠的非洲大陸上，有一個農業發達的帝國，帝國總共有$n$座城市，有$m$條雙向道路將城市相連，資源非常不缺乏，肥料都一袋能頂兩袋撒。帝國會如此壯大的秘密來自於他們首席科學家最自豪的發明 -- 金坷垃，只要在肥料中摻了金坷垃，就不流失、不蒸發、零浪費。可惜好景不常，首席科學家的失蹤導致整個帝國大亂，各地因為沒有金坷垃的供應，叛亂四起、佔山為王、佔路為寇，民不聊生。
每個城市都有一間肥料公賣局，每個城市的肥料公賣局賣的肥料價格都不一樣，如果$A$城市可有一條路徑到達$B$城市，那$AB$城市的人可以互相到對方的城市買肥料。
因為內戰的關係，城市和城市間的道路常常因為戰火而被打斷。身為販賣肥料的商人，卦長經常會在各個城市中旅行，為了能更快速的在城市間移動，卦長曾經向首席科學家學習瞬間移動的能力，可以從一個城市瞬間移動到另一個城市，所以你的移動不會有影響。
卦長現在到了某個城市$p$，想知道現在這個城市的居民能到達的肥料公賣局中，比卦長肥料便宜的有多少間；以及詢問這個城市的居民能到達的肥料公賣局中，價格由小到大排序，排名第$k$的公賣局肥料價格是多少，請你寫個程式告訴卦長吧

輸入說明:

輸入的第一行會有兩個正整數$n,m$，表示城市數量及道路數量，城市、道路的編號由開1始
接著下一行有$n$個整數$C_1,C_2...C_n$，$C_i$表示第$i$個城市的肥料公賣局的肥料售價，$ 0 \leq C_i \leq 2^{31}-1$
再來有$m$行，第$i$行有兩個整數$a_i,b_i$，$ 1 \leq a_i,b_i \leq n$，表示城市$a_i,b_i$間有一條編號為$i$的雙向道路
接著有一個整數$t$($0<t \leq 1000000$)，表示接下來有$t$個事件按造順序發生
事件有四種:
- delete e：戰火將編號為$e$的道路炸毀，$1 \leq e \leq m$，保證已經炸毀的路不會再被炸毀
- rank p w：卦長現在到了某個城市$p$，販賣的肥料價格為$w$，想知道現在這個城市的居民能到達的肥料公賣局中，比卦長肥料便宜的有多少間，$1 \leq p \leq n$，$ 0 \leq w \leq 2^{31}-1$
- kth p k：卦長現在到了某個城市$p$，想詢問這個城市的居民能到達的肥料公賣局中，價格由小到大排序，排名第$k$的公賣局肥料價格是多少，$1 \leq k \leq 居民能走到的城市數量$
- change p w：城市$p$的肥料公賣局將肥料的價格改成$w$

輸出說明

對於每個rank和kth的事件，輸出他們要求的值並換行

範例輸入:

3 3
10 20 30
1 2
2 3
1 3
13
delete 3
kth 1 2
rank 3 15
rank 2 10
rank 1 9
change 2 10
rank 1 10
rank 2 11
kth 2 1
delete 2
kth 3 1
change 1 50
kth 1 1

範例輸出:

配分:

配分	限制
20%	$1 \leq n \leq 10,1 \leq m \leq 1000000$
20%	$1 \leq n \leq 1000,1 \leq m \leq 1000000$
60%	$1 \leq n \leq 100000,1 \leq m \leq 1000000$
時限	2000ms
記憶體	51200000 kb

Judge Setting

run-time limit: 2000 ms
memory limit: 51200000 byte
測資數量: 0