問題文

サイズ L × L × L の立方体型の容器がある。この容器に球を詰め込むゲームを行う。

容器内の点は直交座標系によって表され、容器の頂点の座標のうち一つは (0, 0, 0) であり、その頂点から最も遠い頂点の座標は (L, L, L) である。

詰め込める球は N 個あり、球 1、球 2、…、球 N と呼ばれる。球 i の半径は R_i である。

これらから好きなだけ球を選び、それぞれ容器内の好きな整数座標に配置する (すなわち、球の中心がその整数座標となるように配置する)。

このとき、球が宙に浮いてもよいが、球が容器からはみ出たり球同士が重なったりしてはならない (球と容器、または球同士が接するのはよい)。

球の配置に対し、あなたの点数を以下の総和として計算する。

• 基礎点: 球 i には基礎点 P_i が定められており、球 i を容器内に設置すると P_i 点を得られる。
• ボーナス点: 近くに配置することが好ましい球のペアが M 組与えられる。より具体的には、4 つの整数の組 (A_i, B_i, C_i, D_i) が M 個与えられる。これらはそれぞれ、球 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 より大きい。
• 球同士が重なっている。すなわち、容器内に配置した 2 つの球 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 以外で 1 ケースでも出力が Wrong Answer と判定された場合、example_01 以外のケースの点数はすべて 0 点となる。

サンプルコード (C++)

サンプルコード

このコードをそのまま提出しても構いません。

入力例

入出力例(zip)