알파카 왕국에는 \(N\)개의 목장이 있다. 목장 \(i\)에는 탐험 능력이 \(C_i\)인 알파카 한 마리가 살고 있다.

목장들은 \(N-1\)개의 도로로 연결되어 있으며, 전체 도로망은 트리이다. 각 도로에는 양의 길이가 존재한다.

왕국에서는 서로 다른 두 알파카로 이루어진 2인 원정대를 편성하려 한다. 그러나 모든 알파카와 도로를 항상 이용할 수 있는 것은 아니다. 각 알파카는 현재 원정에 참가하거나 참가하지 않을 수 있고, 각 도로 역시 현재 개방되어 있거나 폐쇄되어 있을 수 있다.

두 알파카 \(u, v\)가 함께 원정대를 이루려면 다음 조건을 모두 만족해야 한다.

• 알파카 \(u\)와 \(v\)가 모두 원정에 참가 중이다.
• \(u\)와 \(v\) 사이의 경로에 있는 모든 도로가 개방되어 있다.

조건을 만족하는 두 알파카의 원정 점수는 다음과 같다.

$$ C_u + C_v + \mathrm{dist}(u, v) $$

여기서 \(\mathrm{dist}(u, v)\)는 처음 주어진 트리에서 \(u\)와 \(v\) 사이의 도로 길이 합이다. 원정 점수는 두 알파카의 탐험 능력과 원정 경로의 길이를 모두 반영한다.

처음에는 모든 도로가 폐쇄되어 있으며, 모든 알파카가 원정에 참가하지 않는다.

알파카 왕은 매우 바빠서 직접 원정대를 꾸릴 수 없다. 여러분이 대신해서 알파카 왕의 명령을 도와주자!

도로와 알파카의 상태를 변경하는 \(Q\)개의 명령이 주어진다. 각 조회 명령마다 현재 편성할 수 있는 모든 2인 원정대 중 최대 원정 점수를 구하여라. 명령의 종류는 다음과 같다.

• 1 e : 입력에서 \(e\)번째로 주어진 도로의 상태를 반전한다. 개방되어 있었다면 폐쇄하고, 폐쇄되어 있었다면 개방한다.
• 2 v : 목장 \(v\)의 알파카가 원정에 참가하는지를 반전한다. 참가 중이었다면 빠지고, 참가하지 않고 있었다면 참가한다.
• 3 : 현재 편성할 수 있는 모든 2인 원정대 중 최대 원정 점수를 출력한다. 편성할 수 있는 원정대가 없다면 \(-1\)을 출력한다.

• \(2 \le N \le 200{,}000\), \(1 \le Q \le 200{,}000\)

• \(0 \le C_i \le 10^9\)

• \(1 \le u, v \le N\), \(1 \le w \le 10^9\)

• 모든 입력값은 정수이다.

첫째 줄에 목장의 수 \(N\)과 명령의 수 \(Q\)가 주어진다.

둘째 줄에 \(N\)개의 정수 \(C_1, C_2, \dots, C_N\)이 주어진다.

다음 \(N-1\)개의 줄에 세 정수 \(u, v, w\)가 주어진다. 이는 목장 \(u\)와 \(v\)를 연결하는 길이 \(w\)의 도로를 의미한다. 도로는 입력에서 주어진 순서대로 \(1, 2, \dots, N-1\)번 번호를 가진다.

다음 \(Q\)개의 줄에 명령이 하나씩 주어진다.

모든 계산에는 64비트 정수형을 사용해야 한다.

각 \(3\)번 명령에 대한 답을 한 줄에 하나씩 출력한다.

cute_alpaca 작성

출처 알파카컵 2회