問題文

サイズ $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)