Tý có một thiết bị nhúng xử lý dãy số \(a_1, a_2, \dots, a_N\). Nó cần chia dãy thành \(K\) khối liên tiếp. Mỗi khối được nén bằng phép XOR toàn bộ các số trong khối. Dung lượng khối là giá trị XOR. Tổng dung lượng là tổng các giá trị XOR.

Hãy chia dãy thành K khối sao cho tổng dung lượng nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên N và Q\( (\)N, Q \le 10^5~).
• ~N-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Dữ liệu vào

• Dòng đầu gồm N, K\( (\)1 \le K \le 200\(, \)K \le N \le 10^5).
• Dòng thứ hai gồm N số a_i\( (\)0 \le a_i < 2^{30}).

Kết quả ra

• In ra tổng dung lượng nhỏ nhất.

Ví dụ

Input

5 2
1 2 3 4 5

Output

1

Giải thích: Chia (1,2,3) → XOR=0, (4,5) → XOR=1, tổng = 1.

Subtask