Reflection timer 1초 memory 1024MB

농부 John은 N \times N 격자로 표현되는 정사각형 캔버스를 가지고 있습니다 (2 ≤ N ≤ 2000, N은 짝수). 그는 다음 단계에 따라 캔버스에 그림을 그립니다:

1. 캔버스를 네 개의 동일한 사분면으로 나눈다. 수직 및 수평 선을 중심을 기준으로 나눈다.

2. 오른쪽 위 사분면에 멋진 그림을 그린다.

   • 칸마다 '#'은 칠해진 부분을, '.'은 비어 있는 부분을 나타낸다.

3. 반사(reflection) 를 수행하여, 그림을 다른 세 개의 사분면에 대칭적으로 복사한다.

예를 들어, N = 8 이고 Farmer John이 다음과 같은 그림을 오른쪽 위 사분면에 그렸다고 하자.

.#..

.#..

.##.

....

이를 중심선을 기준으로 반사하면 최종 캔버스는 다음과 같이 된다.

..#..#..

..#..#..

.##..##.

........

........

.##..##.

..#..#..

..#..#..

그러나 Bessie가 캔버스를 훔쳐 일부를 훼손해버렸다!

• 그녀는 일부 칠해진 셀을 지웠으며,

• 또 다른 셀에 새로운 색을 칠하기도 했다.

이후 Bessie는 캔버스를 원래대로 돌려놓았지만, 원래의 반사 조건을 유지하지 않고 임의로 변형되었다.

Farmer John은 캔버스를 최소한의 수정으로 원래의 반사 조건을 만족하는 상태로 복구하고 싶다.

• 수정 작업은 하나의 셀을 칠하거나('#'), 지우는('.') 것 중 하나이다.

• 최소한의 수정 횟수를 계산해야 한다.

이뿐만 아니라, 이후 U개의 업데이트가 주어지며, 각 업데이트는 특정 셀을 토글(toggle)하는 것이다.

• 즉, 만약 셀이 '#'이라면 '.'으로 바뀌고,

• 만약 셀이 '.'이라면 '#'으로 바뀐다.

각 업데이트 전과 후의 최소 수정 횟수를 출력하라.