1216번 - 충무공 이순신

문제

국토교통부 장관인 수현이는 올해도 다름없이 12월 16일을 맞이할 준비를 하고 있다. 이유는 가장 존경하는 위인이 충무공 이순신이기 때문이다. 그리고 충무공 이순신이 전사함과 동시에 임진왜란이 종전된 날짜가 1598년 12월 16일이므로 수현이에겐 12월 16일이 자신의 생일보다도 중요한 날이 되었다.

수현이는 ‘올해는 무엇으로 12월 16일을 맞이해 볼까?’라고 생각하다가 엄청난 아이디어가 떠올랐다. 바로 충무공 이순신 하면 가장 먼저 떠오르는 거북선을 직접 만들어 보기로 했다. 하지만 아직까지 거북선의 정확한 설계도가 밝혀지지 않아서 1000년 이상 된 소나무를 사용하여 모양만 흉내 내기로 하였다.

우리나라엔 1000년 이상 된 소나무가 있는 지역이 $n$개가 있으며 각 지역은 1ドル$번부터 $n$번까지 고유의 번호가 주어져 있으며, 거북선을 만들 공방은 1ドル$번 지역에 있다. 그리고 두 지역을 잇는 $m$개의 양방향 도로가 주어지며, 초기에 주어지는 모든 도로는 국도다. 도로의 종류는 국도와 고속도로로 2가지가 있다.

각 지역은 그곳으로 가기 위한 힘든 정도가 정해져 있다. 하지만 공방이 있는 1ドル$번 지역에서 도로를 이용해 갈 수 있는 지역의 힘든 정도는 편한 정도로 바뀌며, 공방이 있는 1ドル$번 지역에서 고속도로만을 이용해 갈 수 있는 지역의 편한 정도는 두 배가 된다. 물론, 1ドル$번 지역에서 갈 수 있는 지역이란 뜻은 1ドル$번 지역에서 그 지역까지 경로가 있다는 뜻이며 당연히 공방이 있는 1ドル$번 지역도 해당된다.

이제부터 국토교통부 장관인 수현이는 거북선을 편하게 만들고자 직권을 행사해 임의의 두 지역을 양방향 도로로 연결하려고 한다. 단, 도로교통법에 의해 고속도로는 사이클을 이루지 않아야 하며, 두 지역을 고속도로로 연결하기 위해선 두 지역 사이에 국도로 이동할 수 있는 경로가 존재해야 한다.

한편, 수현이의 직권 남용을 알게 된 감사원장 민지는 화가 났다..! 그래서 민지는 수현이가 연결한 고속도로를 다시 철거하려고 한다. 민지의 친구 해린이는 민지가 화가 난 이유가 궁금해져서 민지를 따라왔다가, 각 지역의 힘든 정도나 편한 정도가 궁금해져서 조사하기로 했다. 하지만 수현이와 민지 그리고 해린이는 할 일이 너무 많아서 코딩의 달인으로 유명한 우리한테 부탁을 했다.

자, 이제 수현이와 민지 그리고 해린이의 부탁을 들어주자.

입력

첫 번째 줄에는 지역의 개수 $n,ドル 도로의 개수 $m$이 공백으로 구분되어 주어진다. $(1 \le n, m \le 121,600円)$

두 번째 줄에는 각 지역으로 가기 위한 힘든 정도 $hard_i$가 1번 지역부터 차례대로 공백으로 구분되어 주어진다. $(1 \le hard_i \le 1,216円)$

세 번째 줄부터 $m$개의 줄에 걸쳐 $a$ 지역과 $b$ 지역을 잇는 국도를 나타내는 두 정수 $a,ドル $b$가 공백으로 구분되어 주어진다. $(1 \le a, b \le n; a \ne b)$

3ドル+m$번째 줄에는 수현이와 민지 그리고 해린의 작업 횟수의 총합 $q$가 주어진다. $(1 \le q \le 121,600円)$

4ドル+m$번째 줄부터 $q$개의 줄에 걸쳐 작업을 나타내는 $p,ドル $a,ドル $b$가 공백으로 구분되어 주어진다. $(1 \le p \le 6; 1 \le a, b \le n; a \ne b)$

$p$는 아래와 같은 내용의 작업을 나타낸다.

• $p = 1$: $a$ 지역과 $b$ 지역을 국도로 잇는다.
• $p = 2$: $a$ 지역과 $b$ 지역을 고속도로로 잇는다. 만약 $a$ 지역에서 $b$ 지역까지 가는 국도 경로가 존재하지 않거나 새로 짓게 되는 고속도로 때문에 고속도로 사이클이 생기면 -1을 출력하고 $a$ 지역과 $b$ 지역을 고속도로로 잇지 않는다.
• $p = 3$: $a$ 지역과 $b$ 지역을 잇는 고속도로를 철거한다. 만약 $a$ 지역과 $b$ 지역을 잇는 고속도로가 없다면 -1을 출력한다.
• $p = 4$: $a$ 지역과 $b$ 지역을 포함한 모든 지역의 힘든 정도의 합을 구해 출력한다.
• $p = 5$: $a$ 지역과 $b$ 지역의 편한 정도의 합을 구해 출력한다.
• $p = 6$: $a$ 지역에서 $b$ 지역까지 가는 고속도로 경로에 있는 모든 지역의 편한 정도의 합을 구해 출력한다. 만약 $a$ 지역에서 $b$ 지역까지 가는 고속도로 경로가 없다면 -1을 출력한다.

모든 작업은 주어지는 순서대로 한 번에 하나씩 진행되며, 입력으로 주어지는 모든 수는 정수이다.

출력

$q$개의 작업 순서대로, 출력을 필요로 할 때마다 알맞게 한 줄에 하나씩 출력한다.

제한

힌트