# Problem L

Bridges and Tunnels 2

It may feel warm now, but in a few months, Waterloo will be full of snow. Luckily, many of the buildings on campus are connected by bridges and tunnels, so you do not need to go outside very much. The network of buildings can be confusing, and it is hard to know the best way to get from one building to another. A computer program could help.

## Input

The first line of input contains three integers $1 \le n \le 4\, 000$, $1 \le m \le 40\, 000$ and
$1 \le p \le 30$, the
number of buildings on campus, the number of (indoor or
outdoor) paths between the buildings, and the number of trips
that you would like to make. Buildings are numbered
sequentially from $0$ to
$n-1$. Each of the next
$m$ lines describes a path
between buildings with three integers and a letter. The first
two integers specify the two buildings connected by the path.
The path can be taken in either direction. The third integer
specifies the number of seconds required to take the path from
one building to the other. The number of seconds is at least
$1$ and at most ten
million. Finally, the letter is `I` if
the path is indoors, or `O` if the path
is outdoors. Each of the next $p$ lines describes a trip between two
buildings using two integers, the numbers of the two
buildings.

## Output

For each trip, find the optimal route between the specified
two buildings. The optimal route minimizes the amount of time
spent outside. Among routes that require spending the same
amount of time outside, the optimal route minimizes the total
time spent. For each trip, output a single line containing two
integers, the time spent outside and the total time spent on
the optimal route. If there is no route connecting the two
specified buildings, output instead a line containing the word
“`IMPOSSIBLE`”.

Sample Input 1 | Sample Output 1 |
---|---|

3 2 4 0 1 30 I 2 2 10 O 0 1 1 0 1 2 2 2 |
0 30 0 30 IMPOSSIBLE 0 0 |