背景

:::epigraph 的冲突， :::

题目描述

本题和试题 D 左灯右行共用相同的背景，两道题之间有较大的关系，建议在尝试其中一题前首先阅读另一题的文本。

这不是一道交互题。

小 T 面对 T 城的地铁图犯了难……

具体而言，这座城市在 E 河两岸，北岸有 $n$ 个地铁站点 $N_1, N_2, \dots, N_n$，南岸有 $n$ 个地铁站点 $S_1, S_2, \dots, S_n$。

T 城总共有 $n-1$ 条地铁线路，每条线路都是环线，其中第 $i$ 条环线连接的地铁站是 $N_i - N_{i+1} - S_{i+1} - S_i - N_i$，但这些地铁环线都是单向运行的，可能是 $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$ 也可能是 $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$。

每条环线都有一个价目表 $u_i, d_i, l_i, r_i$，分别表示这 4 个相邻站（$N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$ 和 $N_{i+1} - S_{i+1}$）之间坐一站地铁移动的价格，注意坐一站地铁的方向由地铁的运行方向而定，可能是 $N_i \to N_{i+1}$ 也可能是 $N_i \leftarrow N_{i+1}$。

高兴的是，时空白洞吐出了价目表上这些环线的运行方向和价格，大 K 准备求助小 T 来得到一些通过地铁移动的价格。

大 K 会告诉小 T 这些环线的运行方向和价目表，随后小 T 需要回答 $q$ 个问题：

• 地铁站 $x$（可以是 $N_i$ 也可以是 $S_i$，下略）到地铁站 $y$ 坐地铁，在给定的地铁价目表下，至少需要支付多少地铁费用？
• 若不同环线连接同一对相邻站，则这些边同时存在并且都可以使用。一次旅行的费用为所经过边权之和，站点间换乘不额外收费。

请帮助小 T 解决这个问题。

输入格式

第一行输入一个整数 $T \ (1 \le T \le 10^5)$，表示测试数据的数量。

每组测试数据第一行输入两个整数 $n$ 和 $q \ (2 \le n \le 10^5, 1 \le q \le 10^5)$，表示参数和询问数量，其中地铁站共 $2n$ 座，环线共 $n-1$ 条。

随后输入 $n-1$ 行，其中第 $i$ 行输入 4 个整数 $u_i, d_i, l_i, r_i \ (0 \le u_i, d_i, l_i, r_i \le 10^9)$，分别表示第 $i$ 条环线上 $N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$ 和 $N_{i+1} - S_{i+1}$ 这四个相邻站之间的移动价格。

随后输入一行一个长度为 $n-1$ 的字符串 $S$，其中第 $i$ 个字符 $S_i \in \{\texttt{I}, \texttt{0}\}$，若 $S_i = \texttt{I}$ 则表示第 $i$ 条环线的方向为 $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$，若 $S_i = \texttt{0}$ 则表示第 $i$ 条环线的方向为 $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$。

随后输入 $q$ 行每行输入 4 个元素 $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\})$，表示大 K 询问小 T 位于 $S_x$ 岸的第 $id_x$ 个地铁站 $(S_x)_{id_x}$ 到位于 $S_y$ 岸的第 $id_y$ 个地铁站 $(S_y)_{id_y}$ 之间至少需要支付多少地铁费用。

保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$, $\sum q \le 3 \times 10^5$。

输出格式

每组测试数据输出 $q$ 行，第 $i$ 行输出一个整数 $d$ 表示小 T 收到的第 $i$ 个询问的答案，也即 $(S_x)_{id_x}$ 到 $(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

提示

样例 1 解释

:::align{center} :::

上面的图展示了第 1 组测试数据中地铁的运行方向和价目表。