Flights

The battlefield is a straight line. Artillery launches ballistic missiles and aviation plans flights over the same line; you must compute the minimal safe altitude for every flight.

A ballistic missile is launched from the ground (altitude $0$) at a point $p$ and flies along a vertically symmetric parabola whose highest point is $(x,\,y)$: its horizontal coordinate is $x$ and its peak altitude is $y$. At a horizontal coordinate $u$ the missile altitude is

$y\left(1-\frac{(u-x)^2}{(x-p)^2}\right),$

and the missile exists only along the arc above the ground, i.e. for $u\in[p,\ 2x-p]$; outside that range it has no trajectory.

Missiles are launched one per minute in input order, so missile $i$ is launched at minute $i$. A flight is given by a time interval $[t_1,\,t_2]$ and a space interval $[x_1,\,x_2]$ (both inclusive). Its minimal safe altitude is the smallest altitude at or below which every missile launched during $[t_1,\,t_2]$ stays throughout the horizontal range $[x_1,\,x_2]$. Equivalently, it is the maximum altitude reached by any such missile over $u\in[x_1,\,x_2]$, counting only the part of each trajectory that is above the ground. If no such missile reaches any point of $[x_1,\,x_2]$, the minimal safe altitude is $0$.

The first line contains one integer $n$ — the number of planned missile launches ($1\le n\le 50000$).

Each of the next $n$ lines contains three integers $p$, $x$, $y$ describing one launch: the launch point $p$ and the highest point $(x,\,y)$ of the trajectory ($0\le p<x\le 50000$, $0<y\le 50$). Missiles are launched one by one every minute in the order given; launch $i$ happens at minute $i$.

The next line contains one integer $m$ — the number of planned flights ($1\le m\le 20000$).

Each of the next $m$ lines contains four integers $t_1$, $t_2$, $x_1$, $x_2$: the time interval $[t_1,\,t_2]$ ($1\le t_1\le t_2\le n$) and the space interval $[x_1,\,x_2]$ ($0\le x_1\le x_2\le 50000$). Both intervals include their endpoints. Minute $1$ is the first launch and minute $n$ is the last.

For each flight, print on its own line the minimal safe altitude as an exact irreducible fraction p/q, where $q\ge 1$ and $\gcd(p,\,q)=1$. The altitude is always a non-negative rational number, so $p\ge 0$; print a zero altitude as 0/1.