Navigation Nightmare

Farmer John's pastoral neighborhood has $N$ farms ($2 \le N \le 40000$), usually numbered 1 to $N$. A series of $M$ vertical and horizontal roads connect the farms, where $1 \le M < 40000$ and each road has a length $L$ with $1 \le L \le 1000$. A map might look like the illustration below, where farms are labeled F1 to F7 and road lengths are shown in parentheses. The diagram is not to scale.

           F1 --- (13) ---- F6 --- (9) ----- F3
            |                                 |
           (3)                                |
            |                                (7)
           F4 --- (20) -------- F2            |
            |                                 |
           (2)                               F5
            | 
           F7 

Each farm connects directly to at most four other farms by roads that run exactly north, south, east, or west. Farms are located only at road endpoints, and every endpoint of every road is a farm. No two roads cross, and exactly one path links every pair of farms.

FJ lost his paper copy of the farm map and wants to rebuild it from backup data on his computer. The data has one line per road, such as:

• There is a road of length 10 running north from Farm #23 to Farm #17
• There is a road of length 7 running east from Farm #1 to Farm #17
• ...

While FJ retrieves the data, his navigationally challenged neighbor Farmer Bob sometimes interrupts with questions such as: What is the Manhattan distance between farms #1 and #23?

FJ answers Bob when he can. In the example above, the answer would be 17. The Manhattan distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $|x_1-x_2| + |y_1-y_2|$, which is the distance a taxi must travel over city streets in a perfect grid to connect the two points.

If FJ does not yet have enough information to deduce the distance between a pair of farms, he apologizes and replies with -1.

The first line contains two space-separated integers $N$ and $M$.

Lines 2 to $M+1$ each contain four space-separated entities $F_1$, $F_2$, $L$, and $D$ that describe a road. $F_1$ and $F_2$ are the numbers of two farms connected by a road, $L$ is its length, and $D$ is one of the characters N, E, S, or W, giving the direction of the road from $F_1$ to $F_2$.

Line $M+2$ contains a single integer $K$ ($1 \le K \le 10000$), the number of queries from Farmer Bob.

Lines $M+3$ to $M+K+2$ each contain three space-separated integers $F_1$, $F_2$, and $I$. $F_1$ and $F_2$ are the numbers of the two farms in the query, and $I$ ($1 \le I \le M$) is the data index after which Bob asks the query. Data index 1 is on line 2 of the input, and so on.

For each of Bob's $K$ queries, print one integer on its own line: the Manhattan distance between the two farms as known after data index $I$, or -1 if the distance cannot yet be determined.

At time 1, FJ knows the distance between 1 and 6 is 13. At time 3, the distance between 1 and 4 is still unknown. At the end, location 6 is 3 units west and 7 north of 2, so the distance is 10.