#216012. [JOI Final 2026] JOI 国的节日 3 / Festivals in JOI Kingdom 3

JOI 国由 座城市和 条高速公路组成。这些城市的编号为 到 ，高速公路的编号为 到 。通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。

每座城市都有一个热度，用一个非负整数表示。城市 （）的初始热度为 。每条高速公路都有一个通行时间，用一个正整数表示。高速公路 （）连接着城市 和城市 ，其初始通行时间为 。

JOI 国的每座城市都有一个圣火盆。JOI 国保持着一个传统，即在节日里，各个城市会点燃它们的圣火盆，这些点火仪式标志着游行队伍从这些城市出发。

如果两座城市由一条高速公路直接相连，则城市 与城市 是相邻的。在某座城市点燃其圣火盆的准确瞬间，将有一支游行队伍从该城市出发前往其每个相邻的城市，所花费的时间等于对应高速公路的通行时间。准确地说，对于两个相邻的城市 和 ，从城市 出发的游行队伍在时间 到达城市 ，其中 是城市 的圣火盆被点燃的时间， 是连接城市 和 的高速公路的通行时间。

有些城市在节日开始的瞬间就会点燃它们的圣火盆，而另一些城市则只有在节日气氛足够热烈后才会这样做。令时间 为节日的开始。对于热度为 的城市 ，城市 点燃其圣火盆的时间按如下方式确定：

• 如果 ，城市 在时间 点燃其圣火盆。
• 如果 ，当从相邻城市到达的游行队伍数量至少达到 时，城市 就会点燃其圣火盆。如果这种情况永远没有发生，城市 就永远不会点燃其圣火盆。

K 先生将在 JOI 国逗留。在他逗留期间，JOI 国将发生 个与其节日相关的事件。这些事件按照发生时间从早到晚编号为 到 。

事件 （）是以下 种类型之一：

• 类型 ：城市 的热度变为 。
• 类型 ：高速公路 的通行时间变为 。
• 类型 ：K 先生访问城市 。假设一个节日在此刻开始，你必须确定城市 是否会点燃其圣火盆，如果会，计算出圣火盆被点燃的时间。

编写一个程序，在给定 JOI 国的结构、每座城市的热度、每条高速公路的通行时间以及事件详情的情况下，对于每个类型 的事件，确定 K 先生访问的城市何时点燃其圣火盆。

从标准输入读取以下数据。

(Query ) 表示事件 （）的详情。在 (Query ) 中，写入了以空格分隔的整数。令 为第一个整数。 为 、 或 ，表示事件 的类型。那么 (Query ) 的含义如下：

• 如果 ，则后面还按此顺序写入了两个整数 。这意味着城市 的热度变为了 。
• 如果 ，则后面还按此顺序写入了两个整数 。这意味着高速公路 的通行时间变为了 。
• 如果 ，则后面还写入了一个整数 。这意味着 K 先生访问了城市 ，并且假设一个节日在此刻开始，你必须确定城市 的圣火盆被点燃的时间。

向标准输出输出，对于每个 的事件 （），按照 递增的顺序，每行输出以下内容：

• 如果 K 先生访问的城市会点燃其圣火盆，输出该圣火盆被点燃的时间。
• 否则，输出 。

样例输入 1

7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1

样例输出 1

80
70
60
-1

样例输入 2

6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1

样例输出 2

30
20
10
30
-1

样例 1

在事件 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 ，城市 点燃了它们的圣火盆。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。 由于城市 会在时间 点燃其圣火盆，因此输出 。

在事件 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 ，城市 点燃了它们的圣火盆。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。 由于城市 会在时间 点燃其圣火盆，因此输出 。

在事件 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 ，城市 点燃了它们的圣火盆。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。
• 在时间 ，城市 点燃了它的圣火盆。到那时，来自城市 的游行队伍已经到达了城市 。 由于城市 会在时间 点燃其圣火盆，因此输出 。

在事件 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 ，城市 点燃了它们的圣火盆。 城市 永远不会点燃它们的圣火盆。由于城市 永远不会点燃其圣火盆，因此输出 。 此样例输入满足子任务 的约束条件。

样例 2

此样例输入满足子任务 的约束条件。

约束条件

• 。
• ()。
• ()。
• ()。
• 通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。
• 。
• 如果 ，则有 , ()。
• 如果 ，则有 , ()。
• 如果 ，则有 ()。
• 给定的值均为整数。

子任务

1. (6 分) , 。
2. (7 分) , ()。如果 ，则有 ()。
3. (14 分) 能被 整除。, ()。如果 ，则有 ()。
4. (25 分) 。如果 ，则有 ()。
5. (12 分) 如果 ，则有 ()。
6. (22 分) ()。
7. (14 分) 无附加约束条件。