#2046 탭 댄스

10 s   128 MB  

Description

 

진우와 동이는 최근 탭 댄스를 배우기 시작했다. 탭 댄스는 전용 신발을 신고 발을 바닥에 구르면서 "탁탁"하는 소리를 내면서 추는 춤이다.

진우와 동이는 탭 댄스에 재능이 있는 친구들이라, 막 기본적인 과정을 마치고 본격적으로 자신들이 출 안무를 직접 짜려고 한다.

탭댄스 안무는 "L"과 "R"로 이뤄진 문자열로 이뤄지고, "L"은 왼쪽발을 바닥에 구르라는 것을 "R"은 오른쪽발을 바닥에 구르라는 것이다. 만약 안무가 "LLRRLL" 이라고 할 경우 처음에는 왼발을 구르고, 또 왼발을 구른다음, 연달아 오른발을 두번 구르고, 마지막에는 왼발을 두번 구르는 것이다. 진우는 탭댄스 안무에서 같은 방향 발을 두번 연달아 사용하지 않아야 춤이 재미있어진다는 것을 알게 되었고, 안무의 점수는 안무에서 "L"이나 "R"이 연속적으로 나오지 않는 연속된 구간 중 가장 긴 구간의 길이라고 정하였다.

진우는 맨 처음에 길이가 N인 "L"로만 이뤄진 안무를 짠 다음, 이를 조금씩 바꿔가면서 그때마다 안무의 점수를 계산하려고 한다. 바꾸는 방법은 안무의 글자 중 하나를 선택하여 "L"일 경우 "R"로, "R"일 경우 "L"로 바꾸는 것이다. 이를 도와주는 프로그램을 작성하자.

Input

 

입력은 여러 개의 테스트 케이스로 이뤄지며, 입력의 맨 첫 줄에는 테스트 케이스의 개수 T가 입력된다.

테스트 케이스의 첫 줄에는 안무의 길이 N과, 안무를 바꾸는 횟수 Q가 입력된다. NQ는 1이상 200,000이하의 정수다. 그다음 줄부터 Q개의 줄에는 안무의 몇 번째 글자를 바꾼다는 것을 의미한다. 맨 앞의 글자는 1번이며, 맨 뒤의 글자는 N번이다.

Output

각 테스트 케이스에 대해 안무를 바꿀 때 마다, 바뀐 안무의 점수를 한줄에 하나씩 출력하라, 또한 i번째 테스트 케이스의 경우 점수들을 출력하기에 앞서 “Case #i:”를 출력한다. 맨 처음 들어오는 테스트 케이스의 번호는 1이며, 마지막에 들어오는 테스트 케이스의 번호는 T이다.

Sample Input

Sample Output

2
6 2
2
4
6 5
4
1
1
2
6
Case #1:
3
5
Case #2:
3
3
3
5
6

HINT

첫 번째 테스트 케이스에서 안무는 다음과 같이 바뀐다: LLLLLL ⇒ LRLLLL ⇒ LRLRLL

Source

http://jungol.co.kr/problem.php?id=2438#none