최신 방문객

원형 도로를 따라 시계 방향으로 1, 2, ..., N번까지 번호가 붙은 N개의 영사관이 있다.

오늘 1, 2, ..., G번 번호의 손님 G명이 이 원형 도로를 M분 동안 달린다. 각 손님은 시계 방향 손님(C)이거나 반시계 방향 손님(A)이다. i번째 손님은 Hi번 영사관에서 출발하며, 매 분이 끝날 때마다 인접한 영사관으로 이동한다.

시계 방향 손님은 j번 영사관에서 j+1번 영사관으로 이동하고, N번 영사관에 있으면 1번 영사관으로 이동한다. 반시계 방향 손님은 j번 영사관에서 j-1번 영사관으로 이동하고, 1번 영사관에 있으면 N번 영사관으로 이동한다.

각 영사관은 마지막으로 방문한 손님만 기억한다. 같은 시각에 마지막으로 방문한 손님이 여럿이면 그 영사관은 그 손님들 모두를 기억한다. 각 손님에 대해, 그 손님을 기억하는 영사관의 수를 구한다.

첫 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 N, G, M이 주어지는 줄로 시작한다. 이후 G줄이 주어지며, i번째 줄에는 정수 Hi와 문자 C 또는 A가 주어진다.

각 테스트 케이스마다 Case #x: y1 y2 ... yG 형식으로 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, yi는 i번째 손님을 기억하는 영사관의 수이다.

1 ≤ T ≤ 100.

모든 i에 대해 1 ≤ Hi ≤ N이다.

첫 번째 예시에서 영사관은 N = 5개, 손님은 G = 3명이며, 이들은 M = 2분 동안 달린다.

• 1번 영사관은 1분이 끝날 때 손님 1과 2가 마지막으로 방문한다.
• 2번 영사관은 2분이 끝날 때 손님 1이 마지막으로 방문한다.
• 3번 영사관은 한 번도 방문되지 않는다.
• 4번 영사관은 2분이 끝날 때 손님 3이 마지막으로 방문한다.
• 5번 영사관은 2분이 끝날 때 손님 2가 마지막으로 방문한다.

따라서 답은 2, 2, 1이다.