After the Twilight Wars, both Venus, Earth and Mars broke into small pieces we now call planetoids. Fortunately humanity survived, and has managed to repopulate the remains of what was once was the Planetarian Trinity. To keep the planetoids united, we formed the InterPlantoidary Programming Competition (IPPC).
To compete in the IPPC, you need to qualify through one of the regional finals. A region is defined as all planetoids whose distance from Sol is within a specified interval $(A_ i, B_ i)$. A planetoid can be part of multiple regions.
Unfortunately, the regional finals seldom happen, as they require low InterPlaNet delays between the planetoids. In fact, they only happen when all planetoids in the region are aligned along the Mean Axis (empty regions are always aligned along the Mean Axis).
Given that all planetoids are aligned along the Mean Axis today, when is the next Old Earth day a region could hold a regional final?
The first line of the input consists of two space-separated
integers $P$ and
$R$, representing the
number of planetoids and regions.
The next $P$ lines each
consist of a number $r_ i$
and an integer $o_ i$,
representing the $i^\textrm
{th}$ planetoidâ€™s orbital radius and orbital period in
Old Earth days. The orbital period represents the number of old
earth days between each time the planetoid is aligned along the
Mean Axis.
The next $R$ lines consist
of two numbers $A_ i$ and
$B_ i$, describing the
interval that defines the $i^\textrm {th}$ region.
For each region, output a line with the number of Old Earth days until the next time a regional final can be arranged in this region.
$1 \leq P, R \leq 100\, 000$
$1 \leq o_ i \leq 1\, 000\, 000$
$0.5 < r_ i < 3.0$
$0.5 \leq A_ i < B_ i \leq 3.0$
No $r_ i$ will be closer to any $A_ j$ or $B_ j$ than $10^{-8}$.
There are less than $10^{18}$ Old Earth days until the next time all planetoids are aligned along the Mean Axis.
Real numbers in the input will have at most $20$ digits after the decimal point.
Sample Input 1 | Sample Output 1 |
---|---|
7 4 1.0 365 1.02 400 1.20 301 0.8 250 0.81 224 1.52 686 1.40 1843 0.9 1.3 1.211119 1.6 0.79 1.1 0.7 0.9 |
8789200 1264298 2044000 28000 |