Background

:::epigraph Conflict, :::

Problem Description

This problem shares the same background as Problem D "Left Light, Keep Right". The two problems are closely related, so it is recommended to read the text of the other one before trying either problem.

This is not an interactive problem.

Little T is puzzled by the metro map of City T...

Specifically, the city lies on both sides of the River E. On the north bank, there are $n$ metro stations $N_1, N_2, \dots, N_n$. On the south bank, there are $n$ metro stations $S_1, S_2, \dots, S_n$.

City T has a total of $n-1$ metro lines. Each line is a loop line. The $i$-th loop connects the stations $N_i - N_{i+1} - S_{i+1} - S_i - N_i$. However, these loop lines all operate in one direction only: it can be either $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$ or $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$.

Each loop line has a price list $u_i, d_i, l_i, r_i$, which represent the cost of taking the metro for one stop between these 4 pairs of 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 travel direction for one stop is determined by the operating direction of the loop line; for example, it may be $N_i \to N_{i+1}$ or $N_i \leftarrow N_{i+1}$.

Fortunately, a spacetime white hole has spat out the operating directions and prices of these loop lines. Big K plans to ask Little T to compute some travel costs by metro.

Big K will tell Little T the operating direction and price list of each loop line. Then Little T needs to answer $q$ questions:

• From station $x$ (it can be $N_i$ or $S_i$, and the same below) to station $y$, under the given metro price lists, what is the minimum metro fare that needs to be paid?
• If different loop lines connect the same pair of adjacent stations, then all such edges exist and can all be used. The cost of one trip is the sum of the weights of the edges taken, and transfers at stations do not cost extra.

Please help Little T solve this problem.

Input Format

The first line contains an integer $T \ (1 \le T \le 10^5)$, the number of testdata.

For each testdata, the first line contains two integers $n$ and $q \ (2 \le n \le 10^5, 1 \le q \le 10^5)$, representing the parameter and the number of queries. There are $2n$ stations in total and $n-1$ loop lines in total.

Then $n-1$ lines follow. In the $i$-th line, 4 integers $u_i, d_i, l_i, r_i \ (0 \le u_i, d_i, l_i, r_i \le 10^9)$ are given, representing the travel costs between the four pairs of adjacent stations on the $i$-th loop: $N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$, and $N_{i+1} - S_{i+1}$.

Then one line contains a string $S$ of length $n-1$. The $i$-th character $S_i \in \{\texttt{I}, \texttt{0}\}$. If $S_i = \texttt{I}$, then the direction of the $i$-th loop is $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$. If $S_i = \texttt{0}$, then the direction of the $i$-th loop is $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$.

Then $q$ lines follow. Each line contains 4 elements $S_x, id_x, S_y, id_y$, $(S_x, S_y \in \{\text{N}, \text{S}\}, id_x, id_y \in \{m \in \mathbb{N} : 1 \le m \le n\})$, meaning Big K asks Little T the minimum metro fare needed to travel from the $id_x$-th station on bank $S_x$, $(S_x)_{id_x}$, to the $id_y$-th station on bank $S_y$, $(S_y)_{id_y}$.

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

Output Format

For each testdata, output $q$ lines. In the $i$-th line, output an integer $d$, the answer to the $i$-th query received by Little T, i.e., the minimum metro fare needed to travel from $(S_x)_{id_x}$ to $(S_y)_{id_y}$.

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

10
12
1
14
0
14
17

Hint

Explanation for Sample 1

:::align{center} :::

The figure above shows the operating directions and price lists of the metro in the first testdata.

Translated by ChatGPT 5