시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 129 53 49 42.241%

문제

개미 나라에 N마리의 개미가 위와 같은 삼거리 위에 있다. 각각의 길의 끝점을 A, B, C이고, 삼거리의 중심은 O이다. 각 삼거리의 길이는 L(길이)로 동일하다.

개미들은 초기 위치와 초기 진행 방향을 가지고 움직인다. 개미들의 속력은 1(길이)/1(초)로 일정하다. 개미들은 다음과 같은 특별한 상황인 경우 규칙에 맞게 진행 방향을 바꾸며, 특별한 상황이 아닌 경우 진행 방향을 유지한다.

규칙 1. 개미들은 서로 다른 개미를 마주칠 경우 (즉, 특정시간에 같은 위치에 있는 경우) 진행 방향을 자신이 진행하고 있던 방향의 반대방향으로 바꾼다. 이는 삼거리의 중심을 포함한 어느 삼거리 위에서도 해당된다.

규칙 2. 중심점으로 특정 한 개미만 도착하는 경우 개미는 갈림길에서 무조건 오른쪽 방향으로 진행 방향을 바꾼다.

위와 같은 규칙으로 움직이다 각각의 길의 끝점인 A, B, C에 도착하는 경우 움직임을 멈춘다. 개미들의 초기 위치와 초기 진행 방향이 주어질 때, 각각의 개미들이 끝점에 도착하기까지 걸리는 시간의 총 합과 각각의 끝점(A, B, C)에 도착하는 개미의 마리 수를 구하여라.

입력

첫 줄에 개미의 총 마리 수인 N (1 ≤ N ≤ 50,000)과 삼거리의 길이인 L (2 ≤ L ≤ 1,000,000,000,000)가 주어진다. 다음 줄부터는 각각의 개미의 초기 위치와 진행 방향이 3개씩 N개의 줄에 걸쳐 주어진다.

각각의 개미가 어느 삼거리 쪽 위에 있는지(A or B or C), 삼거리의 중심으로부터 거리 X (1 ≤ X ≤ L-1), 진행방향은 0 or 1로 주어진다. 0은 그 위치에서 삼거리의 중심 방향이고, 1은 위치한 사거리의 끝점 방향이다. N마리의 개미의 위치는 서로 다르다.

출력

첫 줄에 개미들의 도착하기 까지 걸리는 시간의 총 합을 출력하고, 두 번째 줄에 각각의 끝점(A, B, C)에 도착하는 개미의 마리 수를 출력한다.

예제 입력

5 3
B 2 0
A 1 1
A 2 0
B 1 0
C 2 1

예제 출력

17
2 1 2

힌트

각 초마다 각각의 개미들의 위치는 다음과 같다.

  • 0초 : (B, 2), (A, 1), (A, 2), (B, 1), (C, 2)
  • 1초 : (B, 1), (A, 1), (A, 2), (중심), (C, 3)
  • 2초 : (중심), (중심), (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초에 2번째 개미와 3번째 개미가 마주침.

2초에 1번째 개미와 2번째 개미가 마주침.

1초에 5번째 개미가 C에 도착.

2초에 3번째 개미가 A에 도착.

4초에4번째 개미가C에 도착.

5초에 1번째, 2번째 개미가 각각 B, A에 도착.

총 걸린 시간의 합 17 = 1 + 2 + 4 + 5 + 5.