In the distant future, food is transported between planets via one-way trade routes. Each route directly connects two planets and has a known transit time.

The traders' guild plans to add some new routes utilizing a recently discovered technology – hyperspace travel. Travelling via hyperspace is also one-directional. Since it is still experimental, hyperspace travel time is not yet known, however it is known not to depend on distances between planets, so each hyperspace route will take an equal amount of time to traverse.

The picture below shows an example of three interconnected planets with transit times shown. The planets are labelled with positive integers, and the hyperspace travel time is denoted by $x$ (the picture corresponds to the second example input):

Transit time is measured in days and is always a positive integer.

The traders' guild wishes to analyze the consequences of introducing the new routes: for some two planets $A$ and $B$, they want to know what are all the possible values of the shortest path total transit time from $A$ to $B$, for all possible values of $x$. For example, in the situation above, shortest path travel from planet $2$ to planet $1$ could take $5$ (if $x\ge 5$), $4$, $3$, $2$, or $1$ day (if $x<5$).

Input Specification

The first line of input contains the two integers $P$ and $R$, the number of planets and the number of routes, respectively $(1\le P\le 500,0\le R\le 10000)$.

Each of the following $R$ lines contains two integers $C$ and $D$, the planet labels $(1\le C,D\le P,C\ne D)$, and $T$, the travel time from $C$ to $D$. For conventional routes, $T$ is an integer $(1\le T\le 1000000)$, and for hyperspace routes, $T$ is the character x. Multiple lines can exist between the same two planets.

The following line contains the integer $Q$, the number of queries $(1\le Q\le 10)$.

Each of the following $Q$ lines contains two integers $A$ and $B$, the planet labels $(A\ne B)$ representing a query by the traders' guild: "what are the possible values of shortest path transit time from $A$ to $B$?".

Output Specification

The output must contain $Q$ rows, one per query.

Each row must contain two integers: the number of different values and their sum. If the number of different values is unbounded, output only inf in that row. If there is no path from $A$ to $B$, the number of different values and their sum is $0$.

Scoring

If the output is incorrect, but the first number in each of the $Q$ rows is correct, the solution will be awarded $50\mathrm{\%}$ of points for that test case. Note: The output must contain both numbers in each row where the number of values is bounded in order to qualify.

In test data worth a total of $50$ points, the following constraints hold: $P\le 30$, $R\le 300$, and $T\le 50$.

Sample Input 1

4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4

Sample Output 1

0 0
inf
3 17

Explanation for Sample Output 1

1. There is no possible path from $2$ to $1$.
2. For any positive integer $x$, the shortest path from $1$ to $3$ takes $2x$ time, so the solution is inf.
3. The shortest path from $1$ to $4$ can take $3$ (for $x=1$), $6$ (for $x=2$), or $8$ (for $x\ge 3$) time. $3+6+8=17$.

Sample Input 2

3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3

Sample Output 2

inf
5 65
15 185
5 15
inf
1 10