섬 군도

당신은 해수면이 오르내리면서 섬들이 계속 바뀌는 군도에 살고 있다.

군도는 $n\times n$ 격자로 나타내며, 각 칸은 물이거나 땅이다. 처음에는 군도 전체가 물이다. 격자 바깥은 모두 물로 둘러싸여 있다. 시간이 지나면 일부 물 칸이 낮아져 땅이 드러나고, 일부 땅 칸은 다시 물에 잠긴다.

상하좌우로 이동하면서 땅 칸만 거쳐 한 칸에서 다른 칸으로 갈 수 있으면, 두 땅 칸은 가장자리로 연결된 것이다. 섬은 가장자리로 연결된 땅 칸들의 극대 집합이다. 섬 안에 또 다른 섬이 있을 수도 있다. 예를 들어 어떤 섬이 둘러싼 호수 안에 다른 섬이 있는 경우다.

주민들이 궁금해하는 것 중 하나는 섬이 담수호를 둘러싸고 있는지다. 섬의 땅 칸을 상하좌우로 따라 만든 닫힌 고리가 물 칸을 하나 이상 둘러싸면, 그 섬에는 담수호가 있다. 아래 그림에서 #은 땅, 빈 칸은 물이다. 섬은 모두 다섯 개이고(왼쪽 둘, 가운데 하나, 오른쪽 둘), 담수호를 가진 섬은 오른쪽 바깥쪽 섬 하나뿐이다.

           #####
           #   #
##   ####  # # #
# #  ## #  #  ##
 ##  ###   #####

주민들은 섬의 총 개수와 담수호가 없는 섬의 개수를 알고 싶어 한다.

첫 줄에 격자의 크기 $n$과 질의 개수 $m$이 공백으로 구분되어 주어진다 $(1 \leq n \leq 1\,500, 1 \leq m \leq 5\cdot 10^4)$. 가장 왼쪽 열의 번호는 $c = 1$, 가장 위쪽 행의 번호는 $r = 1$이다.

이어서 $m$개의 줄이 주어지며, 각 줄은 ! 또는 ?로 시작한다.

!로 시작하는 줄에는 공백으로 구분된 두 정수 $r$과 $c$ $(1 \leq r,c\leq n)$가 더 주어진다. $(r,c)$ 칸이 물에서 땅으로, 또는 땅에서 물로 바뀌었다는 뜻이다.

?로 시작하는 줄에는 다른 입력이 없다. 현재 군도의 상태를 묻는 질의다.

각 ? 질의마다 공백으로 구분된 두 정수를 한 줄에 출력한다. 첫 번째는 현재 섬의 개수이고, 두 번째는 그중 담수호를 갖지 않은 섬의 개수다.