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\)

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.