Subtask 1, 2, 3 của bài này có đôi chút khác biệt về giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 3, không có giới hạn gì thêm.

Nhiệm vụ của bạn là tìm một dãy ~a~ gồm ~n~ phần tử thỏa mãn ~m~ yêu cầu. Trong đó yêu cầu thứ ~i~ có dạng ~l_i~ ~r_i~ ~v_i~, nghĩa là:

• Giá trị của ~S(l_i, r_i)~ ~=~ ~a_{l_i}~ ~\oplus~ ~a_{l_i+1}~ ~\oplus~ ... ~\oplus~ ~a_{r_i}~ là chính xác ~v_i~, với ~\oplus~ là phép toán thao tác bit XOR.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, m~ ~(3 \le n, m \le 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ là ~3~ số nguyên dương ~l_i~ ~r_i~ ~v_i~ ~(1 \le l_i < r_i \le n; 0 \le v_i < 2^{30})~.

Output

• In ra ~n~ dòng, dòng thứ ~p~ in ra giá trị của ~a_p~ và một số nguyên dương ~i~ trong đó giá trị của ~a_p~ chắc chắn xác định từ yêu cầu thứ ~i~ ~(1 \le i \le m)~. Trong trường hợp không thể, hãy in ra ~-1~ ~-1~.

Test

Input

5 4
1 4 4
1 3 7
3 4 1
2 3 6

Output

1 4
4 4
2 3
3 2
-1 -1

Note

Với yêu cầu thứ ~i = 1~, ta chỉ biết ~S(1, 4) = 4~ và không thể biết được điều gì. Đến với yêu cầu thứ ~i = 2~, ta có thể tính được ~a_4~ ~=~ ~S(1, 3)~ ~\oplus~ ~S(1, 4)~ ~=~ ~3~. Tiếp tục với ~i = 3~, ta có thể tính được ~a_3 = a_4\oplus S(3, 4) = 2~. Cuối cùng là với yêu cầu thứ ~i = 4~, ta có thể tính được ~a_2~ ~=~ ~a_3~ ~\oplus~ ~S(2, 3)~ ~=~ ~4~ và từ đó, ta có thể tính được thêm ~a_1 = a_2~ ~\oplus~ ~a_3~ ~\oplus~ ~S(1, 3) = 1~.

Với phần tử thứ ~p = 5~, thông tin về nó là không đủ để xác định được giá trị của nó là bao nhiêu.