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 được gọi là ~lca(u, v)~)?

Gọi ~x_i~ là đáp án của truy vấn thứ ~i~ (~1 \leq i \leq q~), 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.

Input

Dòng đầu tiên gồm ~2~ số nguyên dương ~n~ và ~q~ (~1 \leq n \leq 10^5~, ~1 \leq q \leq 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 \leq u, v \leq 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 \leq u_{start}, v_{start} \leq n~, ~0 \leq u_{jump}, v_{jump}, u_{add}, v_{add} \leq 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 > 1~), ~u_i~ = (~u_{i-1}~ ~\cdot~ ~u_{jump}~ + ~u_{add}~) mod ~n + 1~, ~v_i~ = (~v_{i-1}~ ~\cdot~ ~v_{jump}~ + ~v_{add}~) mod ~n + 1~.

Output

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

Scoring

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

1

Notes

• Ở 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 \cdot 1 + 1~ mod ~3 + 1, 3 \cdot 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~.