1. Phát biểu bài toán

Xét một đường ống chân không một chiều được mô hình hóa bởi đoạn thẳng ~[0, L]~ trên trục số thực. Tại thời điểm ~t = 0~, có ~N~ hạt cảm biến kích thước bằng 0 nằm tại các tọa độ nguyên đôi một phân biệt ~0 < X_1 < X_2 < \dots < X_N < L~. Hạt thứ ~i~ có hướng chuyển động ban đầu ~D_i \in \{-1, +1\}~ (với ~-1~ là hướng về 0, ~+1~ là hướng về ~L~) và trạng thái phân cực từ ~P_i \in \{0, 1\}~. Tất cả các hạt chuyển động với tốc độ không đổi là 1 đơn vị độ dài trên mỗi giây.

Hệ thống tuân theo hai quy luật vật lý:

1. Phản xạ biên: Khi một hạt chạm vào biên ~x = 0~ hoặc ~x = L~, nó lập tức đảo ngược hướng chuyển động (~D \leftarrow -D~), nhưng giữ nguyên trạng thái phân cực từ (~P~ không đổi).
2. Tán xạ đàn hồi nội tại: Khi hai hạt gặp nhau tại cùng một tọa độ ~x \in (0, L)~ ở cùng một thời điểm, cả hai lập tức đảo ngược hướng chuyển động của mình, đồng thời trạng thái phân cực từ của mỗi hạt bị đảo ngược (~P \leftarrow P \oplus 1~).

Để loại trừ hiện tượng va chạm ba hạt tại biên, dữ liệu đầu vào đảm bảo tất cả các tọa độ ban đầu ~X_i~ và chiều dài ~L~ đều là các số nguyên chẵn. (Điều này đảm bảo mọi va chạm giữa hai hạt chỉ xảy ra tại tọa độ nguyên và không bao giờ xảy ra tại ~x = 0~ hay ~x = L~).

Yêu cầu: Tại thời điểm ~t = T~ giây, gọi tọa độ và trạng thái phân cực của hạt thứ ~i~ (theo đúng định danh ban đầu lúc ~t = 0~) lần lượt là ~X'_i~ và ~P'_i~. Hãy xác định bộ ~(X'_i, P'_i)~ cho mọi ~i = 1, 2, \dots, N~.

2. Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, L, T~ (~1 \le N \le 2 \cdot 10^5~; ~2 \le L \le 10^9~; ~1 \le T \le 10^{18}~; ~L~ là số nguyên chẵn).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~X_i, D_i, P_i~ (~0 < X_1 < X_2 < \dots < X_N < L~; ~X_i~ là số nguyên chẵn; ~D_i \in \{-1, 1\}~; ~P_i \in \{0, 1\}~).

3. Kết quả

Gồm ~N~ dòng, dòng thứ ~i~ in ra hai số nguyên ~X'_i~ và ~P'_i~ cách nhau bởi một khoảng trắng.

4. Ví dụ

Ví dụ 1:

• Input:

2 10 2
2 1 0
6 -1 1

• Output:

4 1
4 0

• Giải thích:
  • Ban đầu tại ~t = 0~: Hạt 1 tại ~x = 2~, đi sang phải (~+1~), ~P_1 = 0~. Hạt 2 tại ~x = 6~, đi sang trái (~-1~), ~P_2 = 1~.
  • Sau 1 giây (~t = 1~): Hạt 1 đến ~x = 3~, hạt 2 đến ~x = 5~.
  • Sau 2 giây (~t = 2~): Hai hạt gặp nhau tại ~x = 4~. Diễn ra va chạm: cả hai đổi hướng và trạng thái phân cực bị lật:
    • ~P'_1 = 0 \oplus 1 = 1~.
    • ~P'_2 = 1 \oplus 1 = 0~.

5. Subtasks

• Subtask 1 (20% số điểm): ~N \le 15~, ~T \le 100~.
• Subtask 2 (35% số điểm): ~N \le 3000~, ~T \le 10^7~.
• Subtask 3 (45% số điểm): Không có ràng buộc gì thêm (~N \le 2 \cdot 10^5, T \le 10^{18}~).