Three-Way Junction

$N$ ants are on the three-way junction in the figure. The endpoints of the three roads are A, B, and C, and the point where the roads meet is O. All three roads have the same length $L$.

Each ant starts from its own position with its own heading. Every ant moves at a constant speed of length 1 per second. An ant changes its heading in the two situations below, and keeps its heading otherwise.

Rule 1. If two or more ants are at the same point at some moment, that is, they meet, each of them turns to the opposite of the direction it was moving in. This applies at every point of the junction, including the center O.

Rule 2. If exactly one ant arrives at the center O at some moment, that ant always turns onto the road to its right. In the layout of the figure, the road to the right is B for an ant that came from A, C for an ant that came from B, and A for an ant that came from C.

An ant stops where it is once it arrives at one of the endpoints A, B, and C. A stopped ant no longer moves, and it does not affect the movement of the other ants.

The initial position and initial heading of every ant are given. Find the total time the ants spend before arriving at an endpoint, and the number of ants that arrive at each endpoint A, B, and C.

The first line contains the number of ants $N$ ($1 \le N \le 50000$) and the road length $L$ ($2 \le L \le 10^{12}$), separated by a space.

Each of the next $N$ lines describes one ant with three values. The first value is one of the characters A, B, and C, and tells which road the ant is on. The second value is the distance $X$ ($1 \le X \le L-1$) from the center O. The third value is the heading, either 0 or 1, where 0 points toward the center O and 1 points toward the endpoint of that road.

No two of the $N$ ants are at the same position.

On the first line, print the total time the ants spend before arriving at an endpoint.

On the second line, print the number of ants that arrive at the endpoints A, B, and C, in that order, separated by spaces.

In the first example the positions of the five ants at each second are as follows. (A, 2) means the point on road A at distance 2 from the center, and O means the center. Here $L = 3$, so a point at distance 3 is an endpoint.

• second 0: (B, 2), (A, 1), (A, 2), (B, 1), (C, 2)
• second 1: (B, 1), (A, 1), (A, 2), O, (C, 3)
• second 2: O, O, (A, 3), (C, 1), (C, 3)
• second 3: (B, 1), (A, 1), (A, 3), (C, 2), (C, 3)
• second 4: (B, 2), (A, 2), (A, 3), (C, 3), (C, 3)
• second 5: (B, 3), (A, 3), (A, 3), (C, 3), (C, 3)

At second 0.5 the second ant and the third ant meet and reverse. At second 1 the fourth ant arrives at O alone and turns onto road C, the road to its right, and at the same moment the fifth ant arrives at endpoint C. At second 2 the first ant and the second ant meet at O, and the third ant arrives at endpoint A. At second 4 the fourth ant arrives at endpoint C. At second 5 the first ant and the second ant arrive at endpoints B and A. The total time is $1 + 2 + 4 + 5 + 5 = 17$.