C - Place many squares!
Milk
2
s
1024
MB
250
点
問題文
座標$(0,0)$, $(0,10^9)$, $(10^9,10^9)$, $(10^9,0)$で囲まれたグリッドの中に、辺の長さが$2$であり四隅がすべて格子点にある正方形を$N+M$個重ならないように置きたいです。
今、$N$個の正方形がグリッド上に置かれています。置かれている$i$個目の正方形の中心の座標は$(A_i, B_i)$で表されます。
残り$M$個の正方形をグリッド上に重ならないように配置してください。
正方形同士およびグリッドの境界と正方形は辺や点を共有してもよいです。また、すでに置かれている$N$個の正方形同士は重なっていないことが保証されます。
制約下では条件を満たす配置が必ずあることが証明できます。
制約
- $1 \le N,M \le 2000$
- $1 \le A_i,B_i < 10^9$
- 配置されている$N$個の正方形同士は重ならない
入力
$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
出力
$M$行出力してください。$i$行目には、$i$個目に置く正方形の中心の座標を$(a,b)$とした時、以下の形式で出力してください。
$a$ $b$
入力例 1
4 2
1 3
6 6
6 8
2 5
出力例 1
4 7
9 3
入力例1では、グリッド上には次の画像のように正方形が配置されています。
ここに、出力例1の通りに新たに正方形を配置すると、以下の画像のようになります。
全ての正方形同士が重ならずに配置できたため、正解となります。
他にも、次の出力は条件を満たすため正解となります。
1 10
5 1
座標 $(2,2)$ に正方形を置こうとした場合は、1つ目の正方形と重なってしまうため、不正解となります。
