삼거리

개미 나라에 개미 $N$마리가 그림과 같은 삼거리 위에 있다. 세 길의 끝점은 각각 A, B, C이고, 세 길이 만나는 중심은 O다. 세 길의 길이는 모두 $L$로 같다.

개미는 저마다 초기 위치와 초기 진행 방향을 가지고 움직인다. 속력은 모두 1초에 길이 1을 지나는 것으로 일정하다. 개미는 아래 두 상황에서 규칙에 맞게 진행 방향을 바꾸고, 그 밖의 경우에는 진행 방향을 유지한다.

규칙 1. 어떤 시각에 두 마리 이상의 개미가 같은 지점에 있으면, 즉 서로 마주치면, 각 개미는 자신이 진행하던 방향의 반대 방향으로 진행 방향을 바꾼다. 이는 중심 O를 포함해 삼거리 위 어느 지점에서도 적용된다.

규칙 2. 어떤 시각에 중심 O에 개미가 한 마리만 도착하면, 그 개미는 갈림길에서 무조건 오른쪽 길로 진행 방향을 바꾼다. 그림의 배치에서 오른쪽 길은 A에서 온 개미에게 B, B에서 온 개미에게 C, C에서 온 개미에게 A다.

개미는 끝점 A, B, C 중 한 곳에 도착하면 그 자리에 멈춘다. 멈춘 개미는 더 이상 움직이지 않고, 다른 개미의 진행에도 영향을 주지 않는다.

모든 개미의 초기 위치와 초기 진행 방향이 주어진다. 각 개미가 끝점에 도착하기까지 걸린 시간의 총합과 각 끝점 A, B, C에 도착한 개미의 마리 수를 구하라.

첫 줄에 개미의 수 $N$ ($1 \le N \le 50000$)과 길의 길이 $L$ ($2 \le L \le 10^{12}$)이 공백을 사이에 두고 주어진다.

다음 $N$개의 줄에 개미 한 마리의 정보가 한 줄에 세 값씩 주어진다. 첫 값은 개미가 있는 길을 나타내는 문자로 A, B, C 중 하나다. 둘째 값은 중심 O로부터의 거리 $X$ ($1 \le X \le L-1$)다. 셋째 값은 진행 방향으로 0 또는 1이며, 0은 중심 O 쪽, 1은 그 길의 끝점 쪽을 뜻한다.

개미 $N$마리의 위치는 서로 다르다.

첫 줄에 개미들이 끝점에 도착하기까지 걸린 시간의 총합을 출력한다.

둘째 줄에 끝점 A, B, C에 도착한 개미의 마리 수를 차례대로 공백으로 구분해 출력한다.

첫 번째 예제에서 개미 다섯 마리의 매 초 위치는 다음과 같다. (A, 2)는 길 A 위에서 중심으로부터 거리가 2인 지점을 뜻하고, O는 중심을 뜻한다. 이 예제에서 $L = 3$이므로 거리가 3인 지점이 곧 끝점이다.

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

0.5초에 둘째 개미와 셋째 개미가 마주쳐 서로 방향을 바꾼다. 1초에 넷째 개미가 혼자 O에 도착해 오른쪽 길인 C로 방향을 바꾸고, 같은 시각에 다섯째 개미가 끝점 C에 도착한다. 2초에 첫째 개미와 둘째 개미가 O에서 마주치고, 셋째 개미는 끝점 A에 도착한다. 4초에 넷째 개미가 끝점 C에 도착한다. 5초에 첫째 개미와 둘째 개미가 각각 끝점 B와 A에 도착한다. 걸린 시간의 총합은 $1 + 2 + 4 + 5 + 5 = 17$이다.