Equal Product
Contest: Educational Codeforces Round 95 (Rated for Div. 2)
Difficulty rating: 3000
Tags: data structures, math, number theory, two pointers

You are given four integers $$$n$$$, $$$m$$$, $$$l$$$ and $$$r$$$.

Let's name a tuple $$$(x_1, y_1, x_2, y_2)$$$ as good if:

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$$$.

Find any good tuple for each $$$x_1$$$ from $$$1$$$ to $$$n$$$ inclusive.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The second line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le nm$$$).

Output format:
For each $$$x_1$$$ from $$$1$$$ to $$$n$$$ inclusive:

- if there are no such four integers, print $$$-1$$$;
- otherwise, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
8 20
91 100

Example output:
-1
-1
-1
-1
-1
6 16 8 12
-1
-1

Example input:
4 5
1 10

Example output:
1 2 2 1
2 3 3 2
-1
-1

Editorial:
Let's look at $$$x_1 y_1 = x_2 y_2$$$ where $$$x_1 < x_2$$$. It can be proven that there always exists such pair $$$(a, b)$$$ ($$$a \mid x_1$$$, $$$b \mid y_1$$$ and $$$a < b$$$) that $$$x_2 = \frac{x_1}{a} b$$$ and $$$y_2 = \frac{y_1}{b} a$$$.
Brief proof is following: calculate $$$g = \gcd(x_1, x_2)$$$, then let $$$a = \frac{x_1}{g}$$$ and $$$b = \frac{x_2}{g}$$$. Obviously, such $$$(a, b)$$$ will make $$$x_2$$$ from $$$x_1$$$ and $$$y_2$$$ from $$$y_1$$$ (if $$$b \mid y_1$$$). And since $$$b = \frac{x_2}{g} \Rightarrow$$$ $$$b \mid \frac{x_2 y_2}{g} \Rightarrow$$$ $$$b \mid \frac{x_1 y_1}{g} \Rightarrow$$$ $$$b \mid \frac{x_1}{g} y_1$$$ and since $$$\gcd(b, \frac{x_1}{g}) = 1 \Rightarrow$$$ $$$b \mid y_1$$$.
As we can see $$$a$$$ divides $$$x_1$$$, so if we will iterate over all pairs $$$(x_1, a)$$$ where $$$1 \le x_1 \le n$$$ there will be $$$O(n \log n)$$$ pairs in total.
Let's fix value of $$$x_1$$$. Then, from one side, $$$y_1 \le m$$$ but, from the other side, since $$$l \le x_1 y_1 \le r$$$, then $$$\left\lceil \frac{l}{x_1} \right\rceil \le y_1 \le \left\lfloor \frac{r}{x_1} \right\rfloor$$$. Anyway, all valid $$$y_1$$$ form a segment (possibly, empty segment). And we need to find any $$$b > a$$$ that divides any $$$y_1$$$ from the segment and $$$x_2 = \frac{x_1}{a} b$$$ doesn't exceed $$$n$$$. Obviously, it's optimally to find the minimum possible such $$$b$$$ and just check inequality $$$\frac{x_1}{a} b \le n$$$.
We can find such $$$b$$$ for a fixed $$$(x_1, a)$$$ using, for example, built-in upper_bound in a set with all divisors for all valid $$$y_1$$$. To maintain this set we can note that $$$\frac{l}{x_1 + 1} \le \frac{l}{x_1}$$$ (simillary, $$$\frac{r}{x_1 + 1} \le \frac{r}{x_1}$$$). So we can move valid segment's ends as two pointers.
Each pair $$$(y_1, b)$$$ will be added and erased from the segment exactly once. That's why the total complexity of maintaining the set of divisors (as well as the total complexity of queries for each $$$(x_1, a)$$$) will be equal to $$$O((n + m) \log^2 (n + m))$$$.
All pairs $$$(x_1, a)$$$ (and $$$(y_1, b)$$$) can be precalculated in $$$O((n + m) \log (n + m))$$$ using the sieve-like algorithm.