구출 너머

Riatla는 Assassins Order의 잘 알려지지 않은 구성원이다. (유명한 암살자는 짐작하겠지만 오래 살지 못한다.) 임무를 마친 뒤 Riatla에게 문제가 생겼다. 도시 거리마다 경비병이 넘쳐나, 범행 현장에서 빠져나갈 새로운 탈출 계획이 필요하다.

도시는 트리 구조다. 광장 $n$개가 양방향 도로 $n-1$개로 이어져 있고, 임의의 두 광장 사이에는 경로가 정확히 하나 있다.

경비병은 순환 경로를 따라 도시를 순찰한다. 경비병은 광장 수열 $v_1, v_2, \ldots, v_k$를 정한다. 광장 $v_i$를 거친 뒤에는 $v_{i+1}$로 향한다. 두 광장이 도로로 직접 이어져 있지 않으면 경비병은 그 사이의 최단 경로를 따라 이동한다. $v_k$를 거친 뒤에는 $v_1$로 가서 경로를 처음부터 다시 반복한다.

Riatla는 변장을 잘한다. 광장은 붐비므로, 경비병과 같은 광장에 있어도 들키지 않고 그 광장에 머물 수 있다. 반면 도로는 한산해서, Riatla와 경비병이 어느 순간이든 같은 도로 위에 있으면 거리와 관계없이 경비병이 활로 그를 쏜다.

각 도로마다 경비병이 건너는 데 걸리는 시간 $c_i$와 Riatla가 건너는 데 걸리는 시간 $d_i$가 주어진다. 지금 있는 광장 $s$에서 친구들이 기다리는 광장 $t$까지 가는 데 필요한 최소 시간을 구하라. 답은 $998\,244\,353$으로 나눈 나머지로 출력한다.

첫 줄에는 테스트 케이스 수 $t$가 주어진다. 각 테스트 케이스의 첫 줄에는 광장 수 $n$과 경비병 경로의 중요 광장 수 $k$가 주어진다 ($2 \le n, k \le 200\,000$).

이후 $n-1$개 줄에 $u_i$, $v_i$, $c_i$, $d_i$가 주어진다. 이는 도로가 잇는 두 광장, 경비병이 그 도로를 지나는 시간, Riatla가 그 도로를 지나는 시간이다 ($1 \le u_i, v_i \le n$; $1 \le c_i, d_i \le 10^8$). 주어진 그래프는 트리임이 보장된다.

다음 줄에는 경비병 경로의 중요 광장 $a_i$ $k$개가 방문 순서대로 주어진다 ($1 \le a_i \le n$; $a_i \ne a_{i+1}$; $a_1 \ne a_k$).

마지막 줄에는 Riatla의 출발 광장 $s$와 도착 광장 $t$가 주어진다 ($1 \le s, t \le n$; $s \ne t$).

모든 테스트 케이스에서 $n$의 합과 $k$의 합은 각각 $200\,000$을 넘지 않는다.

각 테스트 케이스마다 Riatla가 필요한 최소 시간을 $998\,244\,353$으로 나눈 나머지로 한 줄에 출력한다. Riatla가 들키지 않고 $t$에 도달할 수 없으면 $-1$을 출력한다.