E. Right & Left
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem shares the same background as Problem D Left & Right, and the two problems are closely related. It is recommended to read the text of the other problem first before attempting either of them.

This is not an interactive problem.

Little T is having trouble with the subway map of City T...

Specifically, this city is located on both sides of River E. The north bank has $$$n$$$ subway stations $$$N_1$$$, $$$N_2$$$, $$$\ldots$$$, $$$N_n$$$, and the south bank has $$$n$$$ subway stations $$$S_1$$$, $$$S_2$$$, $$$\ldots$$$, $$$S_n$$$.

City T has a total of $$$n - 1$$$ subway lines, each of which is a loop line. The $$$i$$$-th loop line connects the subway stations $$$N_i - N_{i + 1} - S_{i + 1} - S_i - N_i$$$. However, these subway loop lines operate in a single direction. It might be $$$N_i \leftarrow N_{i + 1} \leftarrow S_{i + 1} \leftarrow S_i \leftarrow N_i$$$ or $$$N_i \rightarrow N_{i + 1} \rightarrow S_{i + 1} \rightarrow S_i \rightarrow N_i$$$.

Each loop line has a price list $$$u_i$$$, $$$d_i$$$, $$$l_i$$$, $$$r_i$$$, respectively representing the price of traveling one subway station between the 4 adjacent stations ($$$N_i - N_{i + 1}$$$, $$$S_i - S_{i + 1}$$$, $$$N_i - S_i$$$, and $$$N_{i + 1} - S_{i + 1}$$$). Note that the direction of traveling one subway station depends on the operating direction of the subway, which might be $$$N_i \rightarrow N_{i + 1}$$$ or $$$N_{i} \leftarrow N_{i + 1}$$$.

Fortunately, a space-time white hole spat out the operating directions and prices of these loop lines on the price lists. Big K plans to seek Little T's help to get the prices for some subway trips.

As a person from another space-time, Big K will tell Little T the operating directions and price lists of these loop lines. Then Little T needs to answer $$$q$$$ questions:

  • How much subway fare must be paid at least to travel by subway from city $$$x$$$ (can be $$$N_i$$$ or $$$S_i$$$, same below) to city $$$y$$$ under the given subway price list?

Please help Little T solve this problem.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5, 1 \le q \le 10^5$$$), representing the parameter for the number of cities and subway lines, and the number of queries.

Each of the following $$$n - 1$$$ lines contains $$$4$$$ integers $$$u_i$$$, $$$d_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$0 \le u_i, d_i, l_i, r_i \le 10^9$$$), respectively representing the moving prices between the four adjacent stations $$$N_i - N_{i + 1}$$$, $$$S_i - S_{i + 1}$$$, $$$N_i - S_i$$$, and $$$N_{i + 1} - S_{i + 1}$$$ on the $$$i$$$-th loop line.

Then, a line containing a string $$$S$$$ of length $$$n - 1$$$ is given, where the $$$i$$$-th character $$$S_i \in \{\mathtt{I}, \mathtt{O}\}$$$. If $$$S_i = \mathtt{I}$$$, it indicates the direction of the $$$i$$$-th loop line is $$$N_i \leftarrow N_{i + 1} \leftarrow S_{i + 1} \leftarrow S_i \leftarrow N_i$$$. If $$$S_i = \mathtt{O}$$$, it indicates the direction of the $$$i$$$-th loop line is $$$N_i \rightarrow N_{i + 1} \rightarrow S_{i + 1} \rightarrow S_i \rightarrow N_i$$$.

Each of the next $$$q$$$ lines contains $$$5$$$ elements $$$S_x$$$, $$$id_x$$$, $$$S_y$$$, $$$id_y$$$ ($$$S_x, S_y \in \{\mathtt{N}, \mathtt{S}\}$$$, $$$id_x, id_y \in \{m \in \mathbb{N} : 1 \le m \le n\}$$$), indicating that Big K asks Little T how much subway fare must be paid at least between the $$$id_x$$$-th city $$$(S_x)_{id_x}$$$ located on the $$$S_x$$$ bank and the $$$id_y$$$-th city $$$(S_y)_{id_y}$$$ located on the $$$S_y$$$ bank.

It is guaranteed that $$$\sum n \le 3 \times 10^5$$$ and $$$\sum q \le 3 \times 10^5$$$ over all test cases.

Output

For each test case, output $$$q$$$ lines. The $$$i$$$-th line should contain an integer $$$d$$$ representing the answer to the $$$i$$$-th query received by Little T, i.e., the minimum required subway fare from $$$(S_x)_{id_x}$$$ to $$$(S_y)_{id_y}$$$.

Example
Input
3
3 5
10 3 1 2
10 10 1 1
OI
N 1 N 2
N 2 N 3
N 2 S 2
S 2 N 2
N 1 N 1
6 1
5 1 7 3
2 6 3 4
6 8 1 7
10 0 7 8
4 5 4 9
IOIOI
N 4 S 4
6 1
4 5 7 6
5 0 9 1
1 5 1 5
10 4 7 1
2 1 3 3
OIOIO
S 6 S 4
Output
10
12
1
14
0
14
17
Note

The figure above shows the operating directions of the subways and the price lists.