동적 격자

각 원소가 0 또는 1인 R행 C열의 격자가 있다. 이 격자에 N개의 연산을 수행하며, 각 연산은 다음 중 하나이다.

• 연산 M: 격자의 한 셀에 있는 수를 0 또는 1로 변경한다.

• 연산 Q: 서로 다른 연결된 1들의 영역 수를 구한다. 연결된 1들의 영역은 모든 셀이 1인 셀의 부분집합이며, 영역 안의 임의의 셀에서 다른 임의의 셀까지 셀의 모서리가 아닌 변을 따라 셀 사이를 이동하여 도달할 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 10. 1 ≤ R, C ≤ 100. 0 ≤ x < R. 0 ≤ y < C. 0 ≤ z ≤ 1.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 격자의 행과 열의 수를 나타내는 두 정수 R과 C가 있는 한 줄로 시작한다. 그다음 각각 C개의 문자로 이루어진 R개의 줄이 주어지며, 각 문자는 0 또는 1이다. 이 줄들은 격자의 초기 상태를 나타낸다.

다음 줄에는 격자에 수행할 연산의 수를 나타내는 정수 N이 주어진다. 이어서 N개의 줄이 더 주어지며, 각 줄에는 하나의 연산이 있다. 모든 연산 M은 M x y z 형식이며, 이는 x행 y열의 셀을 값 z로 변경해야 함을 의미한다. 모든 연산 Q는 Q 형식이다.

각 테스트 케이스마다 "Case #x:"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. 그런 다음 테스트 케이스의 모든 연산 Q에 대해 순서대로 연결된 1들의 영역 수를 포함하는 한 줄을 출력한다.