합동 훈련

특별 훈련 기간을 맞아, 총 $N$개의 부대가 서로 협동하는 합동 훈련이 진행된다. 합동 훈련을 한 번 진행할 때마다 총 $2N$명의 병사를 선발하는데, 각 부대에서 선발할 수 있는 병사의 수에는 제한이 없으며 병사가 한 명도 참여하지 않는 미참여 부대도 있을 수 있다. 훈련에 참여하는 부대에서는 병사들을 훈련지로 수송하기 위해 버스를 대절하는데, 각 부대에서 버스를 대절하는 비용은 각각 $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$개를 넘지 않는다.