합동 훈련

특별 훈련 기간을 맞아 총 $N$개의 부대가 서로 협동하는 합동 훈련을 진행한다. 합동 훈련을 한 번 할 때마다 총 $2N$명의 병사를 선발한다. 각 부대에서 선발할 수 있는 병사의 수에는 제한이 없으며, 병사가 한 명도 참여하지 않는 부대도 있을 수 있다. 훈련에 참여하는 부대는 병사들을 훈련지로 수송하기 위해 버스를 대절하며, 부대 $i$의 버스 대절 비용은 $a_i$이다. 합동 훈련의 비용은 훈련에 참여하는 부대들의 버스 대절 비용을 모두 더한 값이다.

합동 훈련은 $2N$명의 병사가 일렬로 서서 진행한다. 훈련이 끝나면 인접하게 서 있던 병사 쌍마다 소속 부대 간 불만도가 $1$씩 증가한다. 단, 같은 부대끼리 인접해 있었다면 불만도는 증가하지 않는다. 지휘관은 인접한 병사들의 소속 부대 간 불만도가 $K$ 이상인 쌍이 있는 훈련 계획을 승인하지 않는다. 훈련이 시작되기 전에는 모든 부대 사이의 불만도가 $0$이다.

특별 훈련 기간 동안 지휘관은 다음 세 가지 사건에 대한 보고서를 작성해야 한다.

1. 지휘관에게 $2N$명의 병사가 일렬로 나열된 순서대로 소속 부대를 적은 훈련 계획서가 보고된다. 인접한 병사들의 소속 부대 간 불만도가 $K$ 이상인 쌍이 하나라도 있으면 훈련 계획을 승인하지 않아야 하고, 그런 쌍이 없으면 훈련을 진행한 뒤 해당 훈련에 든 비용을 보고해야 한다.
2. 두 부대 $s_i$와 $t_i$ 사이에 다툼이 일어나, 두 부대 사이의 불만도가 $x_i$만큼 증가한다. 어떤 경우에도 훈련을 진행할 수 있는 예산을 얻어내기 위해, 가능한 훈련 계획 중 최대 비용을 보고해야 한다.
3. 물가 상승으로 부대 $s_i$의 버스 대절 비용이 $x_i$만큼 증가했다. 각 부대에 송금해야 하는 비용이 서로 다르면 행정 처리가 복잡해지므로, 부대 $s_i$를 포함하는 합동 훈련 계획 중 서로 다른 비용 개수의 최댓값을 보고해야 한다.

이때 각 사건으로 인한 불만도 증가와 비용 증가는 모든 사건이 끝날 때까지 누적되어 유지된다.

첫 번째 줄에 부대의 개수 $N$과 서로 인접할 수 없는 최소 불만도 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 각 부대의 버스 대절 비용 $a_i$가 공백으로 구분되어 주어진다.

세 번째 줄에 사건이 일어난 횟수 $Q$가 주어진다.

이후 $Q$줄에 걸쳐 사건의 종류 $q_i$와 사건별 변수가 주어진다.

• $q_i=1$이면, 병사들의 소속 부대 번호 $b_i$가 일렬로 나열된 순서대로 공백으로 구분되어 주어진다.
• $q_i=2$이면, 다툼이 일어난 두 부대 번호 $s_i$, $t_i$와 증가한 불만도 $x_i$가 공백으로 구분되어 주어진다.
• $q_i=3$이면, 버스 대절 비용이 증가한 부대 번호 $s_i$와 증가한 비용 $x_i$가 공백으로 구분되어 주어진다.

$i$번째 줄에 $i$번째 사건에 대한 답을 출력한다.

• $q_i=1$이면, 진행된 훈련의 총비용을 출력한다. 훈련이 승인되지 않았다면 -1을 출력한다.
• $q_i=2$이면, 진행할 수 있는 훈련의 최대 비용을 출력한다.
• $q_i=3$이면, 부대 $s_i$를 포함하는 훈련 계획 중 훈련 참여 부대의 서로 다른 비용 개수의 최댓값을 출력한다.

• $1 \leq N \leq 100\,000$; $1 \leq K \leq 10^9$
• $1 \leq a_i \leq 10^9$
• $1 \leq Q \leq 100\,000$
• $1 \leq q_i \leq 3$
• $1 \leq b_i, s_i, t_i \leq N$
• $s_i \neq t_i$
• $1 \leq x_i \leq 10^9$
• 입력되는 모든 수의 개수는 $500\,000$개를 넘지 않는다.