Woburn Challenge 2017-18 Finals Round - Senior Division

The Party of Extraterrestrial Gangsters are not at all pleased with how their invasion of Earth is going so far. Their soldiers on the ground are losing in combat to the well-prepared battalions of cows and monkeys, and their nuclear bomb has been defused with particular ease. Fortunately for them, PEG's space battleship is also outfitted with an enormously powerful vaporizer beam capable of wiping out Scarberia in an instant. The PEG leaders were hoping to avoid resorting to such a merciless tactic, but they're running out of alternatives. However, before proceeding with any vaporization, they'll issue an ultimatum to the Scarberian leaders, detailing the amount of potential destruction and providing an opportunity for unconditional surrender instead.

Downtown Scarberia has a row of $N$ $(1\le N\le 200000)$ skyscrapers, numbered $1$ to $N$ from left to right. Skyscraper $i$ has a height of $H_i$ stories $(1\le H_i\le {10}^9)$, and is occupied by $C_i$ citizens $(1\le C_i\le {10}^9)$.

The PEG leaders have come up with a list of $M$ $(1\le M\le 200000)$ possible plans of attack using their vaporizer beam. The $i$-th plan is defined by three integers, $X_i$, $L_i$, and $R_i$ $(0\le X_i\le N;1\le L_i\le R_i\le N)$. It consists of two phases, as follows:

1. The beam will lock onto the tallest remaining un-vaporized skyscraper, and vaporize it. If there are multiple such skyscrapers with equal heights, they'll choose one of them uniformly at random. They'll repeat this process $X_i$ times, meaning that exactly $X_i$ skyscrapers will get vaporized in this phase.
2. The beam will vaporize all of the un-vaporized skyscrapers numbered between $L_i$ and $R_i$, inclusive. Note that some of these skyscrapers may have already been vaporized in phase 1 of the attack, meaning that anywhere between $0$ and $R_i-L_i+1$ skyscrapers (inclusive) will get vaporized in this phase.

For each possible plan of attack, the PEG leaders are interested in the expected number of citizens who would get vaporized in it (that is, the expected total number of citizens occupying all of the vaporized skyscrapers). Disclosing these statistics in an ultimatum would be sure to drive the Scarberian forces to immediately surrender! Help them determine this value for each of the $M$ plans of attack. Note that none of the plans will actually be executed (yet), meaning that no vaporization will carry over between them.

Subtasks

In test cases worth $7/26$ of the points, $N\le 2000$, $M\le 2000$, and $H_i=1$ for each $i$.
In test cases worth another $6/26$ of the points, $N\le 2000$ and $M\le 2000$.

Input Specification

The first line of input consists of a single integer, $N$.
$N$ lines follow, the $i$-th of which consists of two space-separated integers, $H_i$ and $C_i$, for $i=1\dots N$.
The next line consists of a single integer, $M$.
$M$ lines follow, the $i$-th of which consists of three space-separated integers, $X_i$, $L_i$, and $R_i$, for $i=1\dots M$.

Output Specification

Output $M$ lines, the $i$-th of which contains a single real number, the expected number of citizens who would get vaporized in the $i$-th plan of attack.
Your answer must have at most ${10}^{-5}$ absolute or relative error compared to the judge's answer to be considered correct.

Sample Input

5
4 1
2 50
6 400
4 100
3 33
3
5 1 5
4 2 2
2 2 4

Sample Output

584.0
584.0
550.5

Sample Explanation

In the first plan of attack, all $5$ skyscrapers would already get vaporized in the first phase.

In the second plan of attack, the $4$ tallest skyscrapers would get vaporized in the first phase, leaving just skyscraper $2$ behind, which would happen to get targeted in the second phase anyway.

In the third plan of attack, phase $1$ would involve vaporizing skyscraper 3 followed by either skyscraper $1$ or $4$, with $50\mathrm{\%}$ probability each. In the end, either $550$ or $551$ citizens would be vaporized, with $50\mathrm{\%}$ probability each (depending on the skyscraper chosen in phase $1$).