Problem D
Thermostat Trouble

Image by TheVovaNik (Wikimedia Commons), CC BY-SA 4.0

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 Earth-based 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 (Lifeform-Computer 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 space-separated 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 space-separated 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 space-separated 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.)

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