AT_caddi2019_a 球の詰め込み

有一个 $ L \times L \times L $ 的立方体形状的容器。在这个容器里进行装填球体的游戏。 容器中的点使用直角坐标系表示，一个角点的坐标是 $ (0, 0, 0) $，与它最远的另一个顶点的坐标是 $ (L, L, L) $。 有 $ N $ 个球可以用来填充容器，分别称为球 $ 1 $、球 $ 2 $、......、球 $ N $。每个球 $ i $ 的半径为 $ R_i $。 你可以选择任意数量的球，将它们的中心放置在容器中的任意整数坐标上。 放置球时，球可以悬空，但不能超出容器边界，也不能彼此重叠（球与容器或球之间接触是允许的）。 这次球的配置得分由以下两部分组成： - 基础分：每个球 $ i $ 有一个基础分 $ P_i $，将其放入容器即可获得 $ P_i $ 分。 - 奖励分：存在 $ M $ 对球在靠近放置时可以获得额外奖励分。具体来说，给出 $ M $ 个四元组 $ (A_i, B_i, C_i, D_i) $，它表示如果球 $ A_i $ 和球 $ B_i $ 的中心之间的距离不超过 $ C_i $，则可以得到 $ D_i $ 的奖励分。 请尽量提高你的总得分。不需要找到最优解。

输入为： > $ 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 $。 ## 数据范围 - $ L = 1000 $ - $ N = 1000 $ - $ M = 100000 $ - $ 1 \leq R_i \leq 200 $ - $ 1 \leq P_i \leq 80000 $ - $ 1 \leq A_i < B_i \leq N $ - $ 1 \leq C_i \leq 600 $ - $ 1 \leq D_i \leq 80000 $ 输入中的所有值都是整数。 **本翻译由 AI 自动生成**

### 制約 - $ L\ =\ 1000 $ - $ N\ =\ 1000 $ - $ M\ =\ 100000 $ - $ 1\ ≦\ R_i\ ≦\ 200 $ - $ 1\ ≦\ P_i\ ≦\ 80000 $ - $ 1\ ≦\ 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 以外で $ 1 $ ケースでも出力が *Wrong Answer* と判定された場合、example\_01 以外のケースの点数はすべて $ 0 $ 点となる。 ### サンプルコード (C++) [サンプルコード](https://img.atcoder.jp/caddi2019/9ba3e86cb2b7fc70ac58060984a01872.zip) このコードをそのまま提出しても構いません。 ### Sample Explanation 1 \[入出力例(zip)\](https://img.atcoder.jp/caddi2019/8a480af5f45398c148881593a68ffe14.zip)