Y found two papers and a pencil in his room (It's so valuable for a prisoner). a weighted tree is drawn on the first paper and intialy $0$ is written on the second paper.

He will do following operation for all nonempty matchings of the tree drawn on the first paper:

• First Y will bitwise xor the matching's all edges weights, let's call this value $y$.
• Second consider $x$ is written on the second paper, Y will erase it and write $x \oplus y$ (bitwise xor of $x$ and $y$) on the second paper.

What is the number written on the second paper after Y has done all operations?

Input

First line contains only $n$, number of tree's vertices.

Each of following $n-1$ lines contains $v_i, u_i$ and $w_i$ separated space describing tree's $i$th edge's vertices($v_i, u_i$) and its weight ($w_i$).

$1 \leq n \leq 2 \times 10^5$

$1 \leq v_i, u_i \leq n \\ 0 \leq w_i \leq 10^9$

It is guaranteed that the edges form a tree.

Output

The only line of output contains an integer, the number written on the second paper after Y has done all operations.