There is a circle with a circumference of L. Each point on the circumference has a coordinate value, which represents the arc length from a certain reference point clockwise to the point. On this circumference, there are N ants. These ants are numbered 1 through N in order of increasing coordinate, and ant i is at coordinate Xi.
The N ants have just started walking. For each ant i, you are given the initial direction Wi. Ant i is initially walking clockwise if Wi is 1; counterclockwise if Wi is 2. Every ant walks at a constant speed of 1 per second. Sometimes, two ants bump into each other. Each of these two ants will then turn around and start walking in the opposite direction.
For each ant, find its position after T seconds.
Constraints
All input values are integers.
1≤N≤105
1≤L≤109
1≤T≤109
0≤X1<X2<...<XN≤L−1
1≤Wi≤2
Input
The input is given from Standard Input in the following format:
N L T
X1 W1
X2 W2
.
.
XN WNOutput
Print N lines. The i-th line should contain the coordinate of ant i after T seconds. Here, each coordinate must be between 0 and L−1, inclusive.
1.5 seconds after the ants start walking, ant 1 and 2 bump into each other at coordinate 1.5. 1 second after that, ant 1 and 3 bump into each other at coordinate 0.5. 0.5 seconds after that, that is, 3 seconds after the ants start walking, ants 1, 2 and 3 are at coordinates 1, 3, and 0, respectively.
