Mynerva

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

In Mynerva, there are floating islands connected by bidirectional rainbow bridges. Each bridge has a different brightness and the length of each bridge is . There are animals that are trying to travel from island to another island. These animals can either be white or black. The animals all want to get to their destination while travelling the shortest distance. If there are many paths of the same distance, the white animals will try to maximize the total brightness of the bridges they cross, while the black animals will try to minimize it. Calculate the distance each animal will travel and total brightness they will encounter on their journey.

Input

The first line contains and .

The next lines are in the form representing a path between and with a brightness .

The next line contains .

The next lines contain , the destination of the th animal, followed by either White or Black, representing their color.

Output

For each of the animals output the length and brightness of their best path.

Note: it will always be possible for each animal to reach their destination.

Sample Input

5 7
4 1 7
5 2 1
5 3 9
5 4 5
1 5 1
3 1 8
3 4 6
5
2 Black
5 Black
3 Black
3 White
1 White

Sample Output

2 2
1 1
1 8
1 8
0 0