Hyperspace Routes

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

The traders' guild plans to add new routes using a recently discovered technology: hyperspace travel. Hyperspace travel is also one-directional. Because it is still experimental, the hyperspace travel time is not yet known; it is known, however, that it does not depend on the distance between planets, so every hyperspace route takes the same amount of time to traverse. Let this common time be $x$.

The figure below shows a case with three interconnected planets and their transit times. Planets are labelled with positive integers, and the hyperspace travel time is denoted by $x$ (the figure depicts the graph of the second test case).

Transit time is measured in days and is always a positive integer; the hyperspace time $x$ is likewise a positive integer.

For two planets $A$ and $B$, the guild wants to know all possible values of the shortest-path total transit time from $A$ to $B$, taken over every possible value of $x$. For example, in the situation above, the shortest trip from planet 2 to planet 1 could take $5$ days (when $x \ge 5$), or $4$, $3$, $2$, or $1$ day (when $x < 5$).

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

Each of the next $R$ lines contains two planet labels $C$ and $D$ ($1 \le C, D \le P$, $C \ne D$) and the travel time $T$. For a conventional route, $T$ is an integer ($1 \le T \le 10^6$); for a hyperspace route, $T$ is the character x. Several routes may exist between the same pair of planets.

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

Each of the next $Q$ lines contains two planet labels $A$ and $B$ ($A \ne B$): the guild asks “what are the possible values of the shortest-path transit time from $A$ to $B$?”.

Print $Q$ lines, one per query.

For each query print two integers: the number of distinct possible values and their sum. If the number of distinct values is unbounded, print only inf on that line instead. If there is no path from $A$ to $B$, both the number of distinct values and their sum are $0$ (print 0 0).

Explanation of the first sample:

1. There is no path from planet 2 to planet 1, so the answer is 0 0.
2. For every positive integer $x$, the shortest path from 1 to 3 takes $2x$ days, so the number of values is unbounded and the answer is inf.
3. The shortest path from 1 to 4 can take $3$ days (when $x = 1$), $6$ days (when $x = 2$), or $8$ days (when $x \ge 3$). There are $3$ distinct values and their sum is $3 + 6 + 8 = 17$.