국제 행사

해마다 큰 국제 행사가 열린다. 행사장 앞에는 길고 넓은 거리가 있다. 행사가 시작될 때 주최 측은 거리를 따라 깃대를 세운다. 깃대마다 참가국의 국기를 게양하고 해마다 그 배치를 바꾸는데, 이것이 행사의 상징이 되었다.

깃대는 한 직선 위에 놓여 있고, 깃대 $f_i$는 위치 $\ell_i$에 있다. 위치 $\ell_i$는 모두 정수이고 서로 다르다. 깃대에 게양하는 국기는 국가 집합 $\aleph$에 속한 국가의 것이다. 작년에는 깃대 $f_i$에 국가 $a_i$의 국기가 걸려 있었다. 새해 첫날에는 깃대 $f_i$에 새로 게양할 국가 $b_i$가 정해진다.

깃대 $f_i$의 국기를 $a_i$에서 $b_i$로 바꿔야 한다. 이 일은 국기를 내리고 올리는 로봇 $\Re$가 맡는다. $\Re$는 국기를 사실상 무제한으로 실을 수 있다. 깃대 $f_i$에서 국가 $a_i$의 국기를 내려 실을 수 있고, 그다음 $b_j = a_i$인 깃대 $f_j$의 위치 $\ell_j$로 이동해 그 국기를 게양할 수 있다. 다음 조건이 성립하므로 이 작업은 언제나 가능하다.

각 국가 $c \in \aleph$에 대해, $a_i = c$인 깃대 $f_i$의 개수와 $b_j = c$인 깃대 $f_j$의 개수가 같다.

모든 $\ell_i$와 다른 특별한 위치 $A$가 있고, 로봇 $\Re$는 항상 $A$에서 출발해 $A$에서 끝나야 한다. 위치 $A$에는 깃대가 없다. 즉 $\Re$는 $A$에서 출발해 모든 국기 $a_i$를 $b_j = a_i$인 깃대 $f_j$로 옮긴 뒤 $A$로 돌아온다.

위치 $A$와 깃대의 위치, 그리고 각 깃대 $f_i$의 국가 $a_i$와 $b_i$가 주어질 때, 모든 국기를 옮기는 로봇 $\Re$의 최소 이동 거리를 계산하는 프로그램을 작성하시오.

그림 1에는 깃대를 나타내는 여섯 개의 점과 로봇 $\Re$가 출발하고 도착하는 점 $A$가 있다. 국기의 국가는 집합 $\{1, 2, 3\}$의 정수에 대응한다. 각 점에는 정수 쌍 $(a, b)$가 붙어 있고, $a$는 작년의 국가, $b$는 새해의 국가이다. 화살표는 이동 거리를 가장 짧게 만드는 $\Re$의 이동을 나타낸다. $\Re$는 $A$에서 오른쪽으로 5까지 가서 5에 있는 점의 국가 2 국기를 싣는다. 5에서 1까지 왼쪽으로 이동하면서 3과 5에 있는 점의 국기를 각각 1과 2에 있는 점으로 옮긴다. 이어서 1에서 7까지 오른쪽으로 이동하면서 1, 2, 6에 있는 점의 국기를 각각 3, 5, 7에 있는 점으로 옮긴다. 마지막으로 7에서 $A$까지 왼쪽으로 이동하면서 7에 있는 점의 국기를 6에 있는 점으로 옮기고 끝난다. 이때 $\Re$의 이동 거리는 14이다.

그림 1.

입력은 표준 입력으로 주어진다. 입력은 $T$개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 깃대를 나타내는 점의 개수 $N$ ($2 \le N \le 100{,}000$)이 주어지며, 여기에 $A$는 포함되지 않는다. 둘째 줄에는 $A$의 좌표 $\alpha$ ($1 \le \alpha \le 1{,}000{,}000$)가 주어진다. 셋째 줄에는 국가 집합 $\{1, 2, \dots, M\}$을 나타내는 정수 $M$ ($1 \le M \le 1{,}000$)이 주어진다. 각 정수 $i = 1, \dots, M$에 대해 국가 $i$의 국기가 적어도 하나의 깃대에 게양되어 있다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 세 정수 $\ell_i$, $a_i$, $b_i$가 주어진다. 각각 깃대 $f_i$의 좌표, 작년에 걸려 있던 국기의 국가, 새해에 걸릴 국기의 국가이다. $1 \le \ell_i \le 1{,}000{,}000$이고 $\ell_i \ne \alpha$이며, $1 \le a_i, b_i \le M$이고 $a_i \ne b_i$이다. 또한 모든 $\ell_i$는 서로 다르고 오름차순으로 주어진다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄에는 로봇 $\Re$의 최소 이동 거리를 출력한다.