Island Archipelago

You live on an island archipelago, where the islands keep changing as the sea level rises and falls.

The archipelago is an $n\times n$ grid, where each cell is either water or land. At the start, the whole archipelago is water. Water surrounds the grid on all sides. Over time, some water cells lower to reveal land, and some land cells sink back into water.

Two land cells are edgewise-connected if you can walk between them by moving left, right, up, or down through land cells only. An island is a maximal edgewise-connected group of land cells. Islands can also sit inside other islands. For example, an island can enclose a lake that holds another island.

One concern of the citizens is whether an island encloses a freshwater lake. An island has a freshwater lake if some closed loop of its land cells, formed by steps up, down, left, and right, encircles at least one water cell. In the diagram below, # is land and blank cells are water. There are five islands (two on the left, one in the middle, and two on the right). Only the outer island on the right contains a freshwater lake.

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

The citizens want to know the total number of islands and how many of them do not contain a freshwater lake.

The first line contains two space-separated integers $n$ and $m$ $(1 \leq n \leq 1\,500, 1 \leq m \leq 5\cdot 10^4)$, the size of the grid and the number of queries. The leftmost column has index $c = 1$, and the topmost row has index $r = 1$.

Each of the next $m$ lines begins with either ! or ?.

A line that begins with ! is followed by two space-separated integers $r$ and $c$ $(1 \leq r,c\leq n)$. The cell at $(r,c)$ has changed from water to land, or from land to water.

A line that begins with ? has no other input. It asks for the current state of the archipelago.

For each ? query, print one line with two space-separated integers. The first is the current number of islands. The second is the number of those islands that do not contain a freshwater lake.