Cho một cây gồm \(n\) đỉnh và \(n-1\) cạnh, gốc cây tại nút \(1\).

Trả lời \(q\) truy vấn có dạng:

• \(u\) \(v\): Đâu là tổ tiên chung thấp nhất của \(u\) và \(v\) (hay còn gọi là lca(u,v)? Gọi \(x_i\) là đáp án của truy vấn thứ \(i\), yêu cầu xuất ra giá trị \(ans=x_1 \oplus x_2 \oplus ... \oplus x_q\) với \(\oplus\) là phép toán XOR.

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\) \((1 \le n \le 10^5, 1 \le q \le 10^7)\)
• Trong \(n-1\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \((u,v)\) thể hiện một cạnh của cây \((1 \le u,v \le n, u \neq v)\)
• Các truy vấn sẽ được sinh bằng \(6\) số nguyên \(u_{start},v_{start},u_{jump},v_{jump},u_{add},v_{add}\) \((1 \le u_{start},v_{start} \le n, 0 \le u_{jump},v_{jump},u_{add},v_{add} \le 10^9)\) như sau:
• Trong truy vấn thứ \(1, u_1 = u_{start}, v_1 = v_{start}\)
• Từ truy vấn thứ \(i\) \((i \gt 1)\), \(u_i = (u_{i-1} \times u_{jump} + u_{add})\) mod \(n + 1\), \(v_i = (v_{i-1} \times v_{jump} + v_{add})\) mod \(n + 1\)

Dữ liệu ra

• Gồm \(1\) dòng duy nhất chứa kết quả theo yêu cầu của bài toán.

Input 1

3 1
1 2
1 3
2 3 1 1 1 1

Output 1

1

Input 2

3 2
1 2
1 3
3 3 1 1 1 1

Output 2

1

Giải thích

• Ở test ví dụ đầu tiên, ta có truy vấn \((u_1,v_1)=(2,3)\) có tổ tiên chung thấp nhất là \(1\). Do đó, đáp án cho test này là \(ans=1\)
• Ở test ví dụ thứ hai, ta có \(2\) truy vấn \((u_1,v_1)=(3,3)\) và \((u_2,v_2)=(3 \times 1 + 1\) mod \(n+1, 3 \times 1 + 1\) mod \(3 + 1)=(2,2)\) có tổ tiên chung thấp nhất lần lượt là \(3\) và \(2\). Do đó, đáp án cho test này là \(ans = 3 \oplus 2 = 1\)