[CTSC2016] 时空旅行

题目描述

2045年,人类的技术突飞猛进,已经找到了进行时空旅行的方法。小 R 得到了一台时空旅行仪,他想用它调查不同时空中人类的发展状况。 根据平行时空理论,宇宙中存在着很多独立的时空,每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间,人类使用空间直角坐标系来描述空间中的一个位置,三维坐标分别是 $x,y,z$。 我们假设在初始的时空(编号为 $0$)中,人类存在于地球上(地球的坐标为 $(0,0,0)$),其他的时空都是从一个现有的时空发展而来的。一个时空发生一个时间之后会发展成为另外一个时空(原来的时空不发生任何变化)。会影响小 R 的时间包括两类: 1. 人类殖民了一个新的星球,该星球的状态变成“已被殖民”。 2. 人类放弃了一个已被殖民的星球,该星球的状态变成“未被殖民”。 每次进行时空旅行时,小 R 会先选定一个时空。在这个时空中,人类已经殖民了一些星球。小 R 只要到达该时空中任意一个已被殖民的星球,就能调查人类的发展状况。 小 R 的时空旅行仪出现了一些问题,调整 $x$ 坐标的按钮坏掉了,因此到达点的 $x$ 坐标被固定了(每次旅行的 $x$ 坐标值可能不同)。与此同时,他仍能任意调整到达点的 $y$ 坐标和 $z$ 坐标。 这个问题大大增大了小 R 的花费:因为时空旅行没有花费,但在太空中航行却需要花钱;同时,在不同星球进行调查也可能会产生不同的费用。 假设小 R 将时空旅行的终点设为 $A$,他要进行调查的星球为 $B$:如果 $A$ 与 $B$ 的欧几里得距离为 $d$,那么他太空航行的花费就是 $d^2$;又如果星球 $B$上进行调查的费用为 $c$,那么小 R 此次调查的总花费就是 $d^2+c$。 现在给定小 R 每次旅行到达的时空以及时空旅行仪上固定的 $x$ 坐标值,请你计算出小 R 每次旅行完成调查的最小总花费。

输入输出格式

输入格式


输入的第一行包含三个非负整数 $n,m,c_0$,$n$ 表示平行时空数量,这些平行时空的编号为 $0$ 到 $n-1$ 的整数,初始时空的编号为 $0$。$m$ 表示小 R 进行的时空旅行的次数,$c_0$ 表示在地球进行调查的花费。保证 $0< n,m \leq 5 \times 10^5, 0 \leq c_0 \leq 10^{12}$。 接下来 $n-1$ 行,依次描述平行时空 $1$ 到 $n-1$,其中第 $i$ 行分两种情况: 1. $0 \ \mathrm{fr} \ \mathrm{id} \ x \ y \ z \ c$:表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来,人类殖民了一个编号为 $\mathrm{id}$ 的星球,该星球的坐标为 $(x,y,z)$,在该星球进行调查的花费为 $c$。数据保证给出星球的编号不重复,且 $0< \mathrm{id} < n$;保证 $|x|,|y|,|z| \leq 10^6, 0 \leq c \leq 10^{12}$。 2. $1 \ \mathrm{fr} \ \mathrm{id} $:表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来,人类放弃了编号为 $\mathrm{id}$ 的星球。数据保证该星球在编号为 $\mathrm{fr}$ 的时空中处于被殖民的状态;保证 $\mathrm{id} > 0$,即地球一定不会被放弃。 上述两种情况中,各参数均为正数,相邻整数之间均用一个空格隔开;均保证 $0 \leq \mathrm{fr} < i$。保证不会出现上述两种之外的情况。 接下来 $m$ 行,每行表示小 R 进行的一次时空旅行。每行包括两个正数 $s$ 和 $x_0$,表示小 R 到编号为 $s$ 的平行时空进行了一次时空旅行,时空旅行仪上的 $x$ 坐标被固定为了 $x_0$。保证 $0\le s\lt n$,$|x_0|\le 10^6$。

输出格式


输出 $m$ 行,分别表示每次旅行完成调查的最小总花费。

输入输出样例

输入样例 #1

4 4 2
0 0 1 8 2 3 7
0 1 2 10 1 6 2
1 1 1
1 4
2 8
2 6
3 8

输出样例 #1

18
6
11
66

说明

对于前 $5\%$ 的数据,$n,~m~\leq~100$ 另有 $35\%$ 的数据,$n,~m~\leq~10^5$,其中有 $15\%$ 的数据,人类不会放弃星球,另有 $10\%$ 的数据,每次旅行的 $x$ 相同。 对于剩下的数据,$n,~m~\leq~5~\times~10^5$,其中有 $10\%$ 的数据,每次旅行的 $x$ 相同,$35\%$ 的数据,时空 $i$ 由时空 $i - 1$ 发展而来。在这 $35\%$ 的数据中有 $15\%$ 的数据,人类不会放弃星球。 由于文件压缩包过大无法上传,对于每一个子任务有且仅有一个测试点,为对应分值。