Problem B
When Planetoids Align

Image by kristian fagerström

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?

Input

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.

Output

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.

Limits

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

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