J. Jocund Lecture
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Andrade, Cosenza, and Ebert are in the middle of a lecture, and they are obviously bored. To pass the time, they decide to play a game on a tree. Andrade generates a tree with $$$N$$$ nodes, with node 1 being the root, and each edge has a weight $$$w$$$. Then, Cosenza and Ebert choose two nodes $$$u$$$ and $$$v$$$ from the tree, and the game consists of calculating the sum of the weights of the edges on the path from the root to $$$u$$$ and the sum of the weights of the edges on the path from the root to $$$v$$$. The sum of the weights is calculated modulo $$$10^{5}$$$. Then, the exclusive OR (xor) between the two sums is calculated bit by bit, and the result is the value of the game for that pair of nodes.

They repeat this process several times, choosing different pairs of nodes, and want to know the different results they can obtain.

Input

The first line of the input contains an integer $$$N$$$ $$$(2 \leq N \leq 10^{5})$$$, the number of nodes in the tree. The next $$$N - 1$$$ lines contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ $$$(1 \leq u, v \leq N; 0 \leq w \leq 10^{9})$$$, indicating that there is an edge between nodes $$$u$$$ and $$$v$$$ with weight $$$w$$$.

Output

The first line of the output contains an integer $$$M$$$, the number of distinct possible outcomes of the game. The second line contains $$$M$$$ distinct integers, representing the possible outcomes, in ascending order.

Examples
Input
6
1 2 4
1 3 2
2 4 3
3 6 10
3 5 94
Output
16
0 2 3 4 5 6 7 8 11 12 14 96 98 100 103 108
Input
2
1 2 998244353
Output
2
0 44353