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 1, ~l_i = 1~.

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 = 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

4 3
1 3 0
1 2 3
1 4 4

Output

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

Note

Với yêu cầu thứ ~i = 1~, ta chỉ biết ~S(1, 3) = 0~ 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_3~ ~=~ ~S(1, 2)~ ~\oplus~ ~S(1, 3)~ ~=~ ~3~. Cuối cùng với ~i = 3~, ta có thể tính được ~a_4 = S(1, 3) \oplus S(1, 4) = 4~.

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