U548092 勇气与黑火药(GB)

‌“士兵们，让敌人记住今天的莱比锡！”‌ ——拿破仑的怒吼穿透战场，却难掩命运的裂痕。 联军火炮的铜铸炮身灼热发烫，普鲁士老兵的刺刀寒光凛冽，俄罗斯哥萨克马蹄踏碎法军的方阵线。历史在此刻凝滞：旧大陆的封建秩序与新兴的资产阶级革命理想，在滑膛枪的齐射中激烈碰撞。 1812年拿破仑远征俄国，沙皇亚历山大一世下令焚毁莫斯科以阻截法军，这场大火不仅摧毁了城市，更意外释放了埋藏在克里姆林宫地下的“古老诅咒”——将死者灵魂困于尸体成为活死人——枯萎病。病毒通过尸体接触传播，感染者瞳孔泛红、肢体扭曲，丧失理智但保留战斗本能。这场瘟疫席卷了欧洲，各国被迫组成联军抵御枯萎病的入侵。 “这是神罚吗？”

经历了重重困难，杀死了无数感染者，我们的传奇工兵lwq终于跟着奥地利战士们来到了kaub的城堡，但是lwq发现kaub的楼梯被“神秘力量”变成了一个多口楼梯，形象地来说可以看成是树形结构，而且每个楼梯都连着一个房间，编号为 $i$ ，共有 $n$ 个房间，编号为 $1$ 的房间是kaub城堡的塔顶，每个房间都有一只感染者，每个房间感染者感染度为 $c_i$ ，随着时间推移感染度会改变，而每种感染度为 $j$ 的感染者威胁为 $w_j$ 。 lwq作为传奇工兵当然少不了建防御工事，但是不同的防御工事适用于不同感染程度的怪，所以他需要知道编号为 $u$ 的房间中感染者感染度为 $j$ 的“威胁度”，而编号为 $u$ 的房间中感染度 $j$ 的感染者的“威胁度”为： $ \sum _{ v ⊆ T_{u} } (S_{v,j} × w_j)^2 $ 其中 $S_{v,j}$ 为以 $v$ 为根的子树中感染度为 $j$ 的感染者数量， $T_u$ 表示以 $u$ 为根的子树。 而lwq建造的防御工事能使上述“威胁度”变为： $ \sum _{ v ⊆ T_{ｕ} } (S_{v,j} × w_j - C)^2 $ 但是lwq有一个“威胁下限” $k$ ，他想知道能使建造防御工事后的“威胁度” $≤k$ 的整数 $C$ 的最小值和最大值，以及两者对应的改变后的“威胁度”。

第一行两个整数 $n$ 、 $m$ 和 $q$ ，表示房间的数量、感染度种类和操作数量。 第二行 $m$ 个整数 $w_i$ ，表示感染度为 $i$ 的感染者威胁为 $w_i$ 。 第三行 $n$ 个整数 $c_i$ ，表示一开始编号为 $i$ 的房间中的感染者感染度为 $c_i$ 。 接下来 $n - 1$ 行，第 $i + 3$ 行两个整数 $u_i , v_i$ ,表示 $x_i$ 和 $y_i$ 之间有一条边。 接下来 $q$ 行，第 $i + n + 2$ 行，第一个整数 $op_i$ ： 若 $op_i = 1$ ，给出两个整数 $u_i,t_i$ ，表示编号为 $u_i$ 的房间的感染者感染度变为 $t_i$ 。 若 $op_i = 2$ ，给出三个整数 $u_i,t_i,k_i$ ，询问以 $u_i$ 房间中感染度为 $t_i$ 的感染者 “威胁度”满足 $≤k_i$ 的 $C$ 的最大值和最小值以及对应的“威胁度”的值。 由于lwq太过犇了所以不屑于做这种简单问题，所以请身为老近卫的你来解决这个问题。

对于每个 $op_i = 2$ 的询问，输出两行： 第一行两个整数，表示 $C$ 的最小值以及对应的“威胁度”。 第二行两个整数，表示 $C$ 的最大值以及对应的“威胁度”。 若没有满足的整数 $C$ ，输出两行，每行两个数 $-1$ 。

对于 $100\%$ 的数据，$2 ≤ n ≤ 10^5$ ， $1 ≤ m,q ≤ 10^5$ ，$1 ≤ u_i,v_i ≤ n$ ， $1 ≤ w_i ≤ 100$ ，$1 ≤c_i,t_i ≤ m$ ， $0 ≤k_i ≤ 10^9 $ ，$op_i = {1,2}$ 。 对于 $10\%$ 的数据，$n ≤ 2000$ ， $m,q ≤ 2000$ ， 保证 $-10 ≤ C ≤ 10$ 。 对于另外 $10\%$ 的数据，$n ≤ 2000$ ， $m,q ≤ 2000$ 。 对于另外 $10\%$ 的数据，保证树高不超过 $30$ 。 对于另外 $20\%$ 的数据，保证树的形状是一条链， $m ≤ 10$ 。 对于另外 $20\%$ 的数据，$m ≤ 10$ 。