In Bob's country, there are $N$ cities, numbered from $1$ to $N$. For any two cities $x$ and $y$, there is an undirected road connecting city $x$ and city $y$ with a length of $(x\oplus y)\times D$, where $D$ is a given constant integer, and $\oplus$ represents the bitwise xor operation. Apart from these undirected roads, there are also $M$ one-way highways. The $i$-th highway is from city $u_i$ to city $v_i$ with a length of $w_i$.

Now, Bob wants to travel from city $A$ to city $B$. Can you find the shortest path for Bob?

Input Specification

The first line contains three integers $N$, $M$, and $D$ ($2\le N\le {10}^5$, $0\le M\le 5\times {10}^5$, $1\le D\le 100$), representing the number of cities, the number of highways, and the constant integer $D$, respectively.

Each of the following $M$ lines contains three integers $u_i$, $v_i$, and $w_i$ ($1\le u_i,v_i\le N$, $1\le w_i\le 100$), representing a one-directional highway from cities $u_i$ to $v_i$ with a length of $w_i$.

The last line contains two integers $A$ and $B$, ($1\le A,B\le N$), representing the start city and the destination city.

Output Specification

Output one integer representing the length of the shortest path for Bob from city $A$ to city $B$.

Constraints

Subtask	Points	Additional constraints
$1$	$5$	$M=0$
$2$	$5$	$M=1$
$3$	$5$	$M=3$
$4$	$5$	$M=10$
$5$	$15$	$M=1000$
$6$	$15$	$N=1000$
$7$	$50$	No additional constraints

Sample Input 1

4 2 1
1 3 1
2 4 4
1 4

Sample Output 1

5

Explanation

Bob can take the undirected road from city $1$ to city $4$ with a length of $(1\oplus 4)\times 1=5$.

Sample Input 2

7 2 10
1 3 1
2 4 4
3 6

Sample Output 2

34

Explanation

Bob can take the undirected road from city $3$ to city $2$, then take the highway from city $2$ to city $4$, and finally take the undirected road from city $4$ to city $6$ with a total length of $34$.