Earth has recently been visited by aliens, and is now a
member of a galactic federation consisting of many other
advanced lifeforms on numerous habitable planets. This
federation is very impressive in its scope and accomplishments,
but unfortunately the usual failures of bureaucracy have become
evident as the federation has failed to adopt a universal
system of units. In particular, the units used to represent
temperature vary drastically from world to world, which causes
endless headaches for the galactic tourism industry.
A major problem occurs whenever an individual from one
planet visits another planet and needs to adjust a hotel room
thermostat, as most species are unable to perform the mental
calculations necessary to determine the appropriate thermostat
setting in unfamiliar units. You are an intern at Hubble
Optimal Temperatures (H.O.T.), an Earthbased galactic startup
company, and it is your job to write the backend code for an
app that allows individuals to convert temperatures from any
unit system to any other unit system. (Fortunately, other
employees with more extensive training in LCI
(LifeformComputer Interaction) are responsible for designing
the interface.)
At the beginning of your project you are given a large file
containing temperature conversion information for every unit
system in the galaxy. Specifically, for each unit system
$U$ there are two
integers, $a$ and
$b$ (with $a \neq b$), where $a$ is the temperature value in
$U$ corresponding to
$0$ degrees Celsius, and
$b$ is the temperature
value in $U$ corresponding
to $100$ degrees Celsius.
Note that temperature values in $U$ are always related to Celsius in a
linear fashion. In other words, if $f$ is a function that maps Celsius
values to temperature values in $U$, then there is a constant
$c$ such that for every
fixed real number $\delta
$, $f(t + \delta ) = f(t)
+ c \cdot \delta $ for any temperature $t$ in Celsius.
The unit systems in your input file are indexed $1, 2, 3, \ldots $. The module you are
writing for the app should handle queries consisting of three
integers, $x$,
$y$, $v$, where $x$ is the index of the unit system
you are converting from, $y$ is the index of the unit system
you are converting to, and $v$ is a temperature value in
$x$ that you need to
convert to the corresponding temperature value in $y$.
Input
The first line of input contains two spaceseparated
integers, $N$ and
$Q$ ($1 \leq N \leq 100$, $1 \leq Q \leq 10\, 000$), indicating
the number of unit systems in the galaxy and the number of
queries to your backend module, respectively.
The next $N$ lines
correspond to unit systems indexed $1, 2, 3, \ldots , N$, in that order.
Each line contains two spaceseparated integers, $a$ and $b$ ($10^6 \leq a, b \leq 10^6$,
$a \neq b$), where
$a$ is the unit systemâ€™s
temperature value corresponding to $0$ degrees Celsius, and $b$ is the unit systemâ€™s temperature
value corresponding to $100$ degrees Celsius.
Each of the next $Q$
lines contains three spaceseparated integers, $x$, $y$, $v$ ($1
\leq x,y \leq N$, $10^6
\leq v \leq 10^6$), where $x$ and $y$ are indices of unit systems, and
$v$ is a temperature value
in system $x$ that you
need to convert to the corresponding temperature value in
system $y$.
Output
For each query output a line containing the temperature
value $v$ converted from
unit system $x$ to unit
system $y$ as a fraction
$c/d$, where $c$ and $d$ are integers, the fraction is in
reduced form, and only $c$
is allowed to be negative. (Output 0/1 when the answer is 0.)
Sample Input 1 
Sample Output 1 
3 6
0 100
32 212
88 7
1 2 15
1 2 40
1 2 21
2 1 80
2 1 90
2 3 252

59/1
40/1
349/5
80/3
290/9
11/1
