최근 방문객

Circleburg 시에는 N개의 영사관이 늘어선 커다란 원형 도로가 있다. 영사관에는 시계 방향 순서로 1, 2, ..., N의 번호가 매겨져 있다.

오늘 1, 2, ..., G의 번호가 매겨진 G명의 방문객이 원형 도로를 따라 M분 동안 이동한다. 각 방문객은 시계 방향 방문객(문자 C로 표시)이거나 반시계 방향 방문객(문자 A로 표시)이다.

i번째 방문객은 번호가 $H_{i}$인 영사관에서 출발하며, 매분이 끝날 때마다 인접한 영사관으로 이동한다. i번째 방문객이 j번째 영사관에서 출발한다고 하자. 그 방문객이 다음 중 하나라면:

• 시계 방향 방문객이면, (j+1)번째 영사관으로 이동한다(N번째 영사관에 있다면 1st 영사관으로 이동한다).

• 반시계 방향 방문객이면, (j-1)번째 영사관으로 이동한다(1st 영사관에 있다면 N번째 영사관으로 이동한다).

각 영사관은 자신을 가장 마지막에 방문한 방문객만 기억한다. 가장 마지막에 방문한 방문객이 여러 명이면, 영사관은 그 방문객들을 모두 기억한다.

각 방문객에 대해, 몇 개의 영사관이 그 방문객을 기억하는지 구한다.

제한

시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $H_{i}$ ≤ N.

테스트 세트 1 (공개)

2 ≤ N ≤ 100. 1 ≤ G ≤ 100. 0 ≤ M ≤ 100.

테스트 세트 2 (비공개)

2 ≤ N ≤ $10^{5}$. 1 ≤ G ≤ $10^{5}$. 0 ≤ M ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 N, G, M이 포함된 한 줄로 시작하며, 이들은 각각 영사관의 수, 방문객의 수, 이동할 시간(분)을 나타낸다. 그다음 G개의 줄이 주어진다. i번째 줄에는 정수 $H_{i}$와 문자 하나가 차례로 주어진다. i번째 방문객이 시계 방향 방문객이면 C, 반시계 방향 방문객이면 A가 주어진다.

각 테스트 케이스마다 Case #x: y_{1} y_{2} ... y_{G}을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y_{i}는 i번째 방문객을 기억하는 영사관의 수이다.

첫 번째 예제 케이스에는 N = 5개의 영사관과 G = 3명의 방문객이 있으며, 방문객들은 M = 2분 동안 이동한다.

• 1st 영사관을 가장 마지막에 방문한 사람은 방문객 1와 2이다(1st분이 끝났을 때).

• 2nd 영사관을 가장 마지막에 방문한 사람은 방문객 1이다(2nd분이 끝났을 때).

• 3rd 영사관은 한 번도 방문되지 않는다.

• 4th 영사관을 가장 마지막에 방문한 사람은 방문객 3이다(2nd분이 끝났을 때).

• 5th 영사관을 가장 마지막에 방문한 사람은 방문객 2이다(2nd분이 끝났을 때).

따라서 1st, 2nd, 3rd 방문객의 답은 각각 2, 2, 1이어야 한다.

두 번째 예제 케이스에는 N = 2개의 영사관과 G = 4명의 방문객이 있으며, 방문객들은 M = 0분 동안 이동한다.

• 1st 영사관을 가장 마지막에 방문한 사람은 방문객 1, 2, 3, 4이다(모든 방문객이 이 영사관에서 출발한다).

• 2nd 영사관은 한 번도 방문되지 않는다.

따라서 1st, 2nd, 3rd, 4th 방문객의 답은 각각 1, 1, 1, 1이어야 한다.

세 번째 예제 케이스에는 N = 3개의 영사관과 G = 2명의 방문객이 있으며, 방문객들은 M = 10분 동안 이동한다.

• 1st 영사관을 가장 마지막에 방문한 사람은 방문객 1와 2이다(10th분이 끝났을 때).

• 2nd 영사관을 가장 마지막에 방문한 사람은 방문객 2이다(9th분이 끝났을 때).

• 3rd 영사관을 가장 마지막에 방문한 사람은 방문객 1이다(9th분이 끝났을 때).

따라서 1st와 2nd 방문객의 답은 각각 2, 2이어야 한다.

네 번째 예제 케이스에는 방문객이 단 한 명뿐이다. 이 방문객은 결국 모든 영사관을 방문하므로, 모든 영사관에 기억된다. 따라서 답은 6이다.