← 返回题目列表

Codeforces · 1418/F

F. 等积

中文机器翻译题面 查看原题

给定四个整数 $$$n$$$、$$$m$$$、$$$l$$$ 和 $$$r$$$。

让我们命名一个元组 $$$(x_1, y_1, x_2, y_2)$$$ 为好,如果:

1. $$$1 \le x_1 < x_2 \le n$$$;
2. $$$1 \le y_2 < y_1 \le m$$$;
3. $$$x_1 \cdot y_1 = x_2 \cdot y_2$$$;
4. $$$l \le x_1 \cdot y_1 \le r$$$。

为每个$$$x_1$$$找到从$$$1$$$到$$$n$$$(包括$$$n$$$)的任何好的元组。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$)。

第二行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le nm$$$)。

输出

对于从 $$$1$$$ 到 $$$n$$$(含)的每个 $$$x_1$$$:

- 如果没有这四个整数,则打印$$$-1$$$;
- 否则,打印四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$ 和 $$$y_2$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

8 20
91 100

输出 #1

-1
-1
-1
-1
-1
6 16 8 12
-1
-1

输入 #2

4 5
1 10

输出 #2

1 2 2 1
2 3 3 2
-1
-1

输入 #3

5 12
16 60

输出 #3

-1
2 9 3 6
3 8 4 6
4 5 5 4
-1