Bob lives in a country called HackerLand and in this country, there are \(N\) cities numbered \(1 \) to \(N\) and they form a tree. That is, there are \(N - 1\) undirected roads between these \(N\) cities and every two cities can reach each other through these roads. The length of the road between city \(i\) and city \(j\) is \((i + j)\) (meaning if there is a road between city \(i\) and city \(j\) then the length will be \(i + j\)).
So a great scientist in HackerLand invented the new car in which Bob can travel from one city to another city in \(f(i, j)\) time where \(f(i, j)\) indicates bitwise xor of length of the roads in the simple path between city \(i\) and \(j\). So Bob was curious to find the bitwise xor of all \(f(i, j)\) such that \(1 \leq i \lt j \leq N \). Help Bob to find.
For example, if our country has \(4\) cities then we have to find \( f(1,2) ⊕ f(1,3) ⊕ f(1,4) ⊕ f(2,3) ⊕ f(2,4) ⊕ f(3,4)\) where \(\oplus\) denotes bitwise xor operator.
Input Format
Output Format
Print a single integer denoting our answer
Constraints
\(1 \leq N \leq 10^5 \\ 1 \leq u, v \leq N\)
Note: The country HackerLand has a tree structure
For the given tree in the sample
\(f(1,2) = 3, f(1,3) = 6, f(1,4) = 5, f(1,5) = 14 \\ f(1,6) = 11, f(2,3) = 5, f(2,4) = 6, f(2,5) = 13 \\ f(2,6)=8, f(3,4) = 3, f(3,5) = 8, f(3,6)=13 \\ f(4,5) = 11, f(4,6) = 14, f(5,6)=5\)
If we xor all of them we will get a \(5\).