$n\ q$
$u_1\ v_1\ w_1\ a_1\ b_1\ p_1$
$u_2\ v_2\ w_2\ a_2\ b_2\ p_2$
$\vdots$
$u_{n-1}\ v_{n-1}\ w_{n-1}\ a_{n-1}\ b_{n-1}\ p_{n-1}$
$h_1\ m_1\ s_1\ t_1$
$h_2\ m_2\ s_2\ t_2$
$h_3\ m_3\ s_3\ t_3$
$h_4\ m_4\ s_4\ t_4$

• $n$：車站數量。
• $q$：克勞德的詢問數。
• $u_i, v_i, w_i, a_i, b_i, p_i$ 表示 $i$ 號線連接兩車站 $u_i, v_i$，行車時間 $w_i$ 分鐘，去程首班車為零時 $a_i$ 分發，回程首班車為零時 $b_i$ 分發，且班距固定為 $p_i$ 分鐘。
• $h_i, m_i, s_i, t_i$ 為克勞德的第 $i$ 筆詢問，代表他問你 $h_i$ 點 $m_i$ 分從車站 $s_i$ 到車站 $t_i$ 的所需時間。

$c_1$
$c_2$
$\vdots$
$c_q$

• $c_i$ 為一整數，代表第 $i$ 筆詢問的答案，單位為分鐘。

測資限制

• $2\leq n\leq 5\times 10^ 4$。
• $1\leq q\leq 2\times 10^ 5$。
• $1\leq u_i,v_i\leq n$，$1\leq w_i\leq 1000$。（$i\in\{1,2,\dots,n-1\}$）
• $1\leq p_i\leq 6$，$0\leq a_i,b_i\leq p_i-1$。（$i\in\{1,2,\dots,n-1\}$）
• $0\leq h_i\leq 23$，$0\leq m_i\leq 59$。（$i\in\{1,2,\dots,q\}$）
• $1\leq s_i,t_i\leq n$，且 $s_i\neq t_i$。（$i\in\{1,2,\dots,q\}$）
• 給定的 $n-1$ 條地鐵線恰可以連通 $n$ 座車站。
• 輸入的數皆為整數。

評分說明
本題共有四組子任務，條件限制如下所示。每一子任務可有一或多筆測試資料，該組所有測試資料
皆需答對才會獲得該組分數。

1. (16%) $n\leq 500$。
2. (31%) 對於所有的 $i=1,2\dots,n-1$，皆有 $p_i=1$。
3. (37%) 對於所有的 $i=1,2,\dots,n-1$，皆有 $u_i=i, v_i=i+1$。
4. (16%) 無額外限制。

範例解釋
第一筆詢問中，在 23:35 分從車站 $1$ 出發至車站 $5$ 的乘車過程如下：

1. 首先搭乘 23:37 分往車站 $2$ 的列車，於 23:47 抵達。
2. 接著換乘 23:50 分往車站 $4$ 的列車，於 23:55 抵達（注意需要花一分鐘轉車所以無法搭乘 23:47 發的車）。
3. 最後換乘 23:56 分往車站 $5$ 的列車，於隔天 0:01 抵達目的地。 包含等車與換車的所需時間為 $26$ 分。

第三筆詢問中，搭上 0:01 的列車，於 0:02 抵達目的地，需時 $1$ 分鐘。注意出發時不需要 $1$ 分鐘的轉乘時間即可直接乘車。

2021 TOI 入營考pD
testdata set by Omelet