Description

There are many ants on an infinitely long stick. Each ant has an initial position and an initial direction (no two ants share the same initial position). The ants move forward in their current direction at a speed of 1 unit per second. When two ants meet, they turn around (the turning time is negligible). Given the initial position and initial direction of each ant, please compute their positions and directions after $t$ seconds.

Input Format

The first line contains two space-separated integers $n, t$ (the number of ants $n$ and the time $t$).

Lines $2$ to $n+1$ each contain two integers. Line $i+1$ gives the initial position $a_i$ and initial direction $b_i$ of the $i$-th ant ($b_i = 1$ means facing right, $b_i = -1$ means facing left).

Output Format

Output $n$ lines, each containing two integers. The $i$-th line represents the position and direction of the $i$-th ant after $t$ seconds ($-1$ means facing left, $1$ means facing right, $0$ means currently turning).

4 1
1 1
5 1
3 -1 
10 1

2 0
6 1
2 0
11 1

Hint

Constraints and Conventions

• For $40\%$ of the testdata, $1 \le n \le 100$.
• For $80\%$ of the testdata, $1 \le n \le 10^4$, $0 \le t \le 1000$.
• For $100\%$ of the testdata, $n \le 10^5$, $0 \le t \le 10^5$, $|a_i| \le 10^6$.

Translated by ChatGPT 5