Migrated from Lutece 3283 奖牌摆放（hard version）

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

TAG：扫描线

本题与 easy version 的区别仅在于 $n$ 的范围。

又到了大扫除的时候。看着 232 后面桌子上那座由历届集训队队员获得的奖牌所堆成的小山，QHJ 突然想把它们一块一块在地上摆开，好好瞻仰一下。

QHJ 在 232 挑了一块空地来摆放奖牌，为了方便起见，你可以将奖牌与空地都看成平行于坐标轴的矩形。空地的左下角坐标为 $(0, 0)$，右上角坐标为 $(l, h)$。为了美观起见，QHJ 在摆放奖牌时遵循以下规则：

• 奖牌之间不能有重叠
• 不能旋转奖牌的方向
• 按照奖牌获得时间的先后顺序将奖牌摆到空地上，如果过程中有奖牌放不下了，那就直接把它放回到桌子上。
• 每次摆放一块奖牌时，优先选择能放下它的位置中左下角 $x$ 坐标最小的。如果有多个这样的候选位置，则选择 $y$ 坐标最小的。

现在 QHJ 已经将全部 $n$ 块奖牌按照获得时间顺序排列好了，并测量出了每块奖牌 $x$ 轴方向的长度和 $y$ 轴方向的宽度。请你判断每个奖牌能否放下，如果能则给出其左下角的位置。

Input

第一行三个整数 $n$, $l$, $h$（$1 \le n \le 2000$，$1 \le l, h \le 10^{9}$），分别表示奖牌的个数以及空地的长度和宽度。

接下来 $n$ 行每行两个整数 $x, y$（$1 \le x, y \le 10^{9}$），分别表示每个集装箱 $x$ 轴方向的长度和 $y$ 轴方向的宽度。

Output

按顺序每行对应一个奖牌，如果该奖牌能放下，输出空格分隔的两个整数，表示其左下角的位置坐标。否则，输出 $−1$。

Samples

4 10 10
5 5
6 6
4 7
10 2

0 0
-1
5 0
0 7

Note

请不要真的将奖牌摆开，如果你摆开了请将奖牌擦干净之后再重新摆回去。

Resources

2024 UESTC ICPC Training for Geometry