보안 점검

$N$개의 연구소와 이를 잇는 경로들이 있습니다. 각 연구소에는 그 연구 내용이 얼마나 중요한지를 나타내는 중요도가 주어집니다. $i$번 연구소의 중요도는 $A_i$입니다.

경로는 서로 다른 연구소 2개를 잇고, 경로마다 보안 레벨이 정해져 있습니다. 연구원의 보안 레벨이 경로의 보안 레벨 이상이면 연구원은 그 통로를 이용할 수 있습니다.

연구소에서 정보가 유출될 가능성에 대비해 시뮬레이션을 진행합니다. 보안 레벨 $c$인 연구원이 $i$번 연구소에 잠입해서 그곳에서 도달할 수 있는 모든 연구소의 중요도를 더한 값을 $f(c, i)$라 합니다. 보안 레벨 $c$에 대한 위험도는 $g(c) = \max\{f(c, 1), f(c, 2), \cdots, f(c, N)\}$으로 정의합니다. 이 시뮬레이션의 목표는 정보 유출자가 모은 중요도의 합이 보안 한계점 $D$ 이상이 되는 최소 보안 레벨을 구하는 것입니다. 즉, $g(c) \geq D$를 만족하는 최소 $c$를 구합니다.

연구가 진전되어 중요도가 증가하거나, 새로운 경로가 만들어지거나, 보안이 엄격해져 보안 한계점이 감소할 수 있습니다. 이런 변화가 일어날 때마다 $g(c) \geq D$를 만족하는 최소 $c$를 다시 구합니다.

쿼리는 다음과 같습니다.

• 1 u v l: $u$번 연구소와 $v$번 연구소를 잇는 보안 레벨 $l$의 경로를 추가합니다.
• 2 k a: $k$번 연구소의 중요도를 $a$로 설정합니다. 이 쿼리에서 변경 전 $k$번 연구소의 중요도는 $a$ 이하임이 보장됩니다.
• 3 d: 보안 한계점을 $d$로 변경합니다. 이 쿼리에서 변경 전 보안 한계점은 $d$ 이상임이 보장됩니다.
• 4: $g(c) \geq D$를 만족하는 최소 $c$를 출력합니다.

첫 번째 줄에 연구소의 개수 $N$, 경로의 개수 $M$, 초기 보안 한계점 $D$이 공백으로 구분되어 주어집니다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 차례대로 공백으로 구분되어 주어집니다. $A_i$는 $i$번 연구소의 중요도입니다.

세 번째 줄부터 $M$개의 줄에 걸쳐 $i$번째 경로를 나타내는 세 정수 $s_i$, $e_i$, $l_i$가 공백으로 구분되어 주어집니다. 이는 $s_i$번 연구소와 $e_i$번 연구소를 잇는 보안 레벨 $l_i$의 간선이라는 뜻입니다.

$M+3$번째 줄에 쿼리의 개수 $Q$가 주어집니다. 이후 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어집니다. 2번 쿼리에서 중요도는 감소하지 않으며, 3번 쿼리에서 보안 한계점은 증가하지 않음이 보장됩니다.

4번 쿼리의 결과를 쿼리의 입력 순서대로 한 줄에 하나씩 출력합니다. 모든 $c$가 조건을 만족하면 $-1$을, 모든 $c$가 조건을 만족하지 않으면 $-2$를 출력합니다.

• 주어지는 모든 수는 정수입니다.
• $2 \le N \le 100\,000$
• $0 \le M \le 150\,000$
• $1 \le D \le 10^{18}$
• $1 \le A_i \le 1\,000\,000$ ($1 \leq i \leq N$)
• $1 \le s_i, e_i \le N$, $s_i \neq e_i$, $1 \le l_i \le 600\,000$ ($1 \leq i \leq M$)
• $1 \le Q \le 100\,000$
• $1 \le u, v \le N$, $u \neq v$, $1 \le l \le 600\,000$
• $1 \le k \le N$, $1 \le a \le 1\,000\,000$
• $1 \le d \le 10^{18}$
• 2번 쿼리에서 중요도는 감소하지 않으며, 3번 쿼리에서 보안 한계점은 증가하지 않음이 보장됩니다.