충무공 이순신

지역은 1번부터 n번까지 번호가 붙어 있고, 거북선을 만들 공방은 1번 지역에 있다. 각 지역 i에는 그 지역까지 가기 어려운 정도 hard_i가 있다.

도로에는 국도와 고속도로가 있다. 처음 주어지는 m개의 도로는 모두 국도이다. 국도로 연결된 같은 연결 요소 안의 지역들은 서로 국도만으로 이동할 수 있다.

현재 국도 연결 요소 중 1번 지역이 속한 연결 요소에 있는 지역은 더 이상 힘든 지역이 아니며, 각 지역의 hard_i가 그 지역의 편한 정도가 된다. 1번 지역에서 고속도로만 사용해 도달할 수 있는 지역은 편한 정도가 2 * hard_i가 된다. 1번 지역의 국도 연결 요소에 속하지 않는 지역은 편한 정도가 0으로 계산된다.

고속도로는 항상 전체 고속도로 그래프가 사이클을 만들지 않도록 관리되어야 한다. 또한 두 지역을 고속도로로 직접 잇기 위해서는, 두 지역 사이에 현재 국도만으로 이동할 수 있는 경로가 있어야 한다.

q개의 작업이 차례대로 주어진다. 국도 추가, 고속도로 추가와 철거, 그리고 현재 상태에 대한 질의 결과를 처리하라.

첫째 줄에 지역의 수 n과 처음 국도의 수 m이 공백으로 구분되어 주어진다. (1 <= n, m <= 121600)

둘째 줄에 hard_1, hard_2, ..., hard_n이 공백으로 구분되어 주어진다. (1 <= hard_i <= 1216)

다음 m개의 줄에는 국도 하나를 나타내는 두 정수 a, b가 공백으로 구분되어 주어진다. (1 <= a, b <= n, a != b)

그다음 줄에 작업의 수 q가 주어진다. (1 <= q <= 121600)

다음 q개의 줄에는 작업을 나타내는 세 정수 p, a, b가 공백으로 구분되어 주어진다. (1 <= p <= 6, 1 <= a, b <= n, a != b)

각 작업의 의미는 다음과 같다.

• p = 1: a 지역과 b 지역을 국도로 잇는다.
• p = 2: a 지역과 b 지역을 고속도로로 잇는다. 두 지역 사이에 국도 경로가 없거나, 이 고속도로를 추가하면 고속도로 사이클이 생기는 경우에는 -1을 출력하고 추가하지 않는다.
• p = 3: a 지역과 b 지역을 직접 잇는 고속도로를 철거한다. 그런 고속도로가 없으면 -1을 출력한다.
• p = 4: 현재 힘든 상태로 남아 있는 모든 지역의 hard 값 합을 출력한다. 이 작업에서 a와 b는 형식을 맞추기 위해 주어진다.
• p = 5: a 지역과 b 지역의 편한 정도의 합을 출력한다.
• p = 6: a 지역에서 b 지역까지 고속도로만으로 가는 경로 위의 모든 지역의 편한 정도 합을 출력한다. 그런 고속도로 경로가 없으면 -1을 출력한다.

모든 작업은 입력 순서대로 하나씩 처리된다.

출력이 필요한 작업마다 정답을 한 줄에 하나씩 출력한다.