Kiến trên vòng tròn

Trong một chuyến dã ngoại tại công viên, FullHouse Dev bắt gặp một hiện tượng thú vị: những chú kiến đang di chuyển trên một vòng tròn. Điều này khiến họ nghĩ ra một bài toán thú vị về sự di chuyển của kiến.

Bài toán

Trong một quốc gia, tất cả kiến di chuyển trên một vòng tròn. Vòng tròn được đánh dấu với \(n\) điểm đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ. Có \(m\) con kiến trên vòng tròn. Ban đầu, không có hai con kiến nào đứng trên cùng một điểm đánh dấu. Chúng ta biết hướng di chuyển của mỗi con kiến. Nếu hai con kiến gặp nhau trong quá trình di chuyển, mỗi con sẽ bắt đầu di chuyển theo hướng ngược lại. Nhiệm vụ của FullHouse Dev là xác định vị trí của các con kiến sau \(t\) giây di chuyển.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(t\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(p_i\) và \(d_i\):
  • \(p_i\) là vị trí ban đầu của con kiến thứ \(i\).
  • \(d_i\) là hướng di chuyển của con kiến: \(1\) nếu di chuyển theo chiều kim đồng hồ, \(-1\) nếu ngược chiều kim đồng hồ.

OUTPUT FORMAT:

• In ra một dòng chứa \(m\) số nguyên theo thứ tự tăng dần, biểu thị vị trí của các con kiến sau \(t\) giây.

Ràng buộc:

• \(2 \leq n \leq 10^9\)
• \(1 \leq m \leq 10^5\)
• \(0 \leq t \leq 10^9\)
• \(1 \leq p_i \leq n\)
• \(d_i = 1\) hoặc \(d_i = -1\)

Ví dụ

INPUT

5 2 1
2 1
3 -1

OUTPUT

2 3

Giải thích

Trong ví dụ này, con kiến thứ nhất và con kiến thứ hai đổi vị trí cho nhau sau 1 giây.