32127번 - 보안 점검 서브태스크

문제

$N$개의 연구소와, 이를 잇는 경로들이 존재한다. 각 연구소마다 그 연구소의 연구 내용이 얼마나 중요한지를 나타내는 척도인 중요도가 주어진다. $i$번 연구소의 중요도는 $A_i$이다.

하나의 경로는 서로 다른 2ドル$개의 연구소를 이으며, 경로마다 보안 레벨이 존재한다. 연구원의 보안 레벨이 경로의 보안 레벨 이상일 경우, 연구원은 통로를 이용할 수 있다.

연구소에서 정보가 유출될 가능성에 대비하여 시뮬레이션을 진행하였다. 보안 레벨 $c$인 연구원이 $i$번 연구소에 잠입하여 그 연구소에서 도달 가능한 모든 연구소의 중요도를 전부 더한 값을 $f(c, i)$이라 하자. 보안 레벨 $c$에 대하여, 위험도를 $g(c) = \max\left\{f(c, 1), f(c, 2), \cdots, f(c, N)\right\}$이라고 정의하자. 이 시뮬레이션의 목표는, 정보 유출자가 모은 정보의 중요도의 합이 보안 한계점 $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$가 공백으로 구분되어 주어진다. 이는 $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번 쿼리에서 보안 한계점은 증가하지 않음이 보장된다.

서브태스크

힌트