Ada and Roads
As you might already know, Ada the Ladybug is a farmer. She grows many fruits and vegetables. She has to take care of them so she builds many roads between them. She also doesn't want to keep unnecessary roads so after building a road she cleans the rest of roads so her road-system doesn't contain any needless cycles. Each road has some maintenance cost and she always keeps roads in such ways that the total cost is minimized.
Input
The first line of input contains 1 ≤ N ≤ 2*105, 0 ≤ M ≤ 5*105, the number of vegetables and the number of roads built by Ada.
The next M lines contains three integers a, b, c: 0 ≤ a, b < N, 0 ≤ c ≤ 109, a ≠ b, the vegetables connected by road and its maintenance cost.
To simulate the "real-time", a, b, c will be on input as a ⊕ l, b ⊕ l, c ⊕ l, where l is the last answer (start as 0) and operation stands for binary XOR.
Output
For each new road print the number actual best sum of maintenance costs.
Example Input
5 5 4 3 6 6 7 4 8 9 10 8 12 9 8 10 11
Example Output
6 8 8 9 5
Real queries
REAL QUERY: 4 3 6 REAL QUERY: 0 1 2 REAL QUERY: 0 1 2 REAL QUERY: 0 4 1 REAL QUERY: 1 3 2
Example Input 2
6 9 3 2 7 4 5 13 2 6 3 11 10 14 17 18 18 16 23 26 19 18 17 18 19 21 14 13 12
Example Output 2
7 7 11 16 18 18 16 14 11
Real queries 2
REAL QUERY: 3 2 7 REAL QUERY: 3 2 10 REAL QUERY: 5 1 4 REAL QUERY: 0 1 5 REAL QUERY: 1 2 2 REAL QUERY: 2 5 8 REAL QUERY: 1 0 3 REAL QUERY: 2 3 5 REAL QUERY: 0 3 2
Example Input 3
3 4 0 1 8 8 10 13 15 13 4 13 12 8
Example Output 3
8 13 13 10
Example Input 4
6 7 4 3 3 3 6 4 14 9 13 8 15 14 11 13 9 17 16 20 13 14 6
Example Output 4
3 10 10 14 21 15 24
Example Input 5
7 11 3 0 997179154 997179152 997179154 204554238 1926119418 1926119416 1370896084 2521188650 2521188654 3204670819 3213587831 3213587825 2592574673 3142795976 3142795983 3067341340 3369331620 3369331617 3266995941 3544021221 3544021220 3341161807 2952422819 2952422823 3068368185 2952422818 2952422823 3137316850 2952422817 2952422819 2934379046
Example Output 5
997179154 1926119422 2521188648 3213587827 3142795978 3369331616 3544021221 2952422819 2952422819 2952422819 2349523846