问题描述

有一个尺寸为$L × L × L$的立方体容器。进行将球放入容器的游戏。

容器内的点用直角坐标系表示，容器的顶点坐标之一为$(0, 0, 0)$，最远顶点的坐标为$(L, L, L)$。

可以放入容器中的球共有$N$个，分别称为球$1$、球$2$、...、球$N$。球$i$的半径为$R_i$。

从这些球中任选球，并将它们分别放置在容器内的整数坐标位置（即球心处于整数坐标位置）。

此时，球可以悬浮在空中，但不能让球溢出容器，球之间也不能重叠（球与容器或球与球可以相切）。

对于球的布局，根据以下总和计算你的得分。

• 基础分：球$i$具有基础分$P_i$，将球$i$放置在容器内可得到$P_i$分。
• 奖励分：给定了$M$对最好放置在附近的球。具体来说，给定了$M$个四元组$(A_i, B_i, C_i, D_i)$。这些四元组分别表示当将球$A_i$和球$B_i$放置在容器内使得它们的中心之间的欧几里得距离不超过$C_i$时，可得到$D_i$分。（禁止以距离超过$C_i$的方式放置球）

考虑布局使得可以获得尽可能多的分数。无需求出最优解。

约束条件

• $L = 1000$
• $N = 1000$
• $M = 100000$
• $1 ≤ R_i ≤ 200$
• $1 ≤ P_i ≤ 80000$
• $1 ≤ A_i < B_i ≤ N$
• $1 ≤ C_i ≤ 600$
• $1 ≤ D_i ≤ 80000$
• 输入中的所有值都是整数。

输入

输入以以下格式给出。

$L$ $N$ $M$ $R_1$ $P_1$ $R_2$ $P_2$ $:$ $R_N$ $P_N$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $:$ $A_M$ $B_M$ $C_M$ $D_M$

输出

将球$i$的中心坐标表示为$(X_i, Y_i, Z_i)$，以以下格式输出。如果球的中心不在容器内，则将其坐标表示为$(-1, -1, -1)$。

$X_1$ $Y_1$ $Z_1$ $X_2$ $Y_2$ $Z_2$ $:$ $X_N$ $Y_N$ $Z_N$

以下情况将被判定为_Wrong Answer_。

• 输出格式错误（包括$X_i, Y_i, Z_i$不是整数的情况）。
• 球溢出容器。即对于放置在容器中的球$i$，满足$X_i - R_i$, $Y_i - R_i$, $Z_i - R_i$中至少一个小于$0$，或者满足$X_i + R_i$, $Y_i + R_i$, $Z_i + R_i$中至少一个大于$L$。
• 球之间重叠。即对于放置在容器中的两个球$i$，$j$（$i < j$），满足球$i$和$j$的中心之间的欧几里得距离小于$R_i + R_j$。

输入生成

无需详细理解本部分内容。

每个球$i$的参数确定如下：

• 球$i$的半径$R_i$在$1$到$200$之间的整数中随机确定。
• 基础分$P_i$在$1$到$\max(1,R_i^3/100)$之间的整数中随机确定。

此外，第$i$个奖励点的参数确定如下：

• $A_i, B_i$是随机确定的$1$到$N$之间的$2$个整数。如果选择相同的值，则重新选择。然后，如果$A_i > B_i$，则交换$A_i$和$B_i$的值。
• $C_i$是从$R_{A_i} + R_{B_i} + 1$到$R_{A_i} + R_{B_i} + 200$之间的整数中随机确定。
• $D_i$是从$1$到$2R_{A_i}R_{B_i}$之间的整数中随机确定。

评分

在单个测试用例中得分按照问题描述中所述的基础分和奖励分的总和计算。

共有50个测试用例，所有测试用例的分数总和即为提交的得分。

另外，如果在除了example_01以外的任何一个测试用例中输出被判定为_Wrong Answer_，则除了example_01之外的所有测试用例的得分都为0。

示例代码（C++）

示例代码

可以直接提交此代码。

输入示例

输入输出示例(zip)