In Bob's country, there are cities, numbered from to . For any two cities and , there is an undirected road connecting city and city with a length of , where is a given constant integer, and represents the bitwise xor operation. Apart from these undirected roads, there are also one-way highways. The -th highway is from city to city with a length of .

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

#### Input Specification

The first line contains three integers , , and (, , ), representing the number of cities, the number of highways, and the constant integer , respectively.

Each of the following lines contains three integers , , and (, ), representing a one-directional highway from cities to with a length of .

The last line contains two integers and , (), representing the start city and the destination city.

#### Output Specification

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

#### Constraints

Subtask | Points | Additional constraints |
---|---|---|

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 to city with a length of .

#### 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 to city , then take the highway from city to city , and finally take the undirected road from city to city with a total length of .

## Comments