International Event

A large international event is held every year. A long, wide street runs in front of the event hall. When the event opens, the organizers put up flagpoles along the street. They raise national flags on the flagpoles and rearrange them every year. This has become the symbol of the event.

The flagpoles stand on a line, and flagpole $f_i$ is at location $\ell_i$. The locations $\ell_i$ are integers and all distinct. Every flag raised on a flagpole belongs to a nation in the set $\aleph$. Last year the flag of nation $a_i$ was raised on flagpole $f_i$. On the first day of the new year, the nation $b_i$ whose flag is newly raised on flagpole $f_i$ is decided.

The flag on flagpole $f_i$ has to change from $a_i$ to $b_i$. A robot $\Re$ does this work by lowering and raising flags. $\Re$ can carry an almost unlimited number of flags. It may lower the flag of nation $a_i$ on flagpole $f_i$ and carry it. It may then move to the location $\ell_j$ of a flagpole $f_j$ with $b_j = a_i$ and raise the flag there. This work is always possible because the following condition holds.

For each nation $c \in \aleph$, the number of flagpoles $f_i$ with $a_i = c$ equals the number of flagpoles $f_j$ with $b_j = c$.

There is a special location $A$, different from every $\ell_i$, where the robot $\Re$ must always start and finish. No flagpole stands at $A$. So $\Re$ starts at $A$, delivers every flag of nation $a_i$ to a flagpole $f_j$ with $b_j = a_i$, and ends at $A$.

Given the location $A$, the locations of the flagpoles, and the nations $a_i$ and $b_i$ of each flagpole $f_i$, write a program that computes the minimum travel distance of the robot $\Re$ to deliver all the flags.

Figure 1 shows six points representing the flagpoles and the special point $A$ where the robot $\Re$ starts and finishes. The nations of the flags correspond to the integers in the set $\{1, 2, 3\}$. Each point carries a pair of integers $(a, b)$, where $a$ is the nation of last year's flag and $b$ is the nation of the new year's flag. The arrows show a movement of $\Re$ that makes the travel distance as short as possible. $\Re$ moves right from $A$ to 5 and loads the flag of nation 2 from the point at 5. Moving left from 5 to 1, it delivers the flags of the points at 3 and 5 to the points at 1 and 2. Then it moves right from 1 to 7 and delivers the flags of the points at 1, 2, and 6 to the points at 3, 5, and 7. Finally it moves left from 7 to $A$ and delivers the flag of the point at 7 to the point at 6 on the way. The travel distance of $\Re$ is 14.

Figure 1.

Your program reads from standard input. The input consists of $T$ test cases. The first line of the input contains the number of test cases $T$. Each test case starts with a line containing an integer $N$ ($2 \le N \le 100{,}000$), the number of points representing the flagpoles, which does not count $A$. The second line contains an integer $\alpha$ ($1 \le \alpha \le 1{,}000{,}000$), the coordinate of $A$. The third line contains an integer $M$ ($1 \le M \le 1{,}000$), which stands for the set of nations $\{1, 2, \dots, M\}$. For each integer $i = 1, \dots, M$, at least one flag of nation $i$ is raised on a flagpole. The $i$-th of the following $N$ lines contains three integers $\ell_i$, $a_i$, and $b_i$: the coordinate of flagpole $f_i$, the nation of its flag last year, and the nation of its flag in the new year. Here $1 \le \ell_i \le 1{,}000{,}000$ with $\ell_i \ne \alpha$, and $1 \le a_i, b_i \le M$ with $a_i \ne b_i$. All $\ell_i$ are distinct and are given in increasing order.

Your program writes to standard output. Print exactly one line for each test case. The line contains the minimum travel distance of the robot $\Re$.