Bajtazar is training to become a professional player in Forkbajt. The game of Forkbajt takes place on an $n \times n$ board, where rows and columns are numbered with integers from $1$ to $n$. Bajtazar's castle is located at the field in row $1$ and column $1$. Each of the remaining fields may contain an obstacle or a fort. The entire game lasts for $q + 1$ days, and each night between two of these days, we receive information about the construction or demolition of a certain fort.

Every day, Bajtazar must send messages to all currently existing forts. A day consists of many turns. In each turn, Bajtazar can recruit a new hero and instruct them to travel from the castle to one of the forts (to deliver a message there). Subsequently, each hero can move to an adjacent field (left, right, up, or down). A hero can pass through a field containing a fort, but cannot pass through a field containing an obstacle. It is also not allowed for two heroes to be on the same field at the end of a turn. We are interested in determining the minimum number of turns required to deliver messages to all forts.

Your task is to determine, for each of the $q + 1$ days, the minimum number of turns required to deliver messages to all currently existing forts. We guarantee that no fort will ever be "cut off" from the castle, meaning it will always be possible to travel from the castle to any currently existing fort.

Input

The first line of the input contains two integers $n$ and $q$ ($2 \le n \le 1\,000$, $0 \le q \le 500\,000$) denoting the size of the board and the number of days. The next $n$ lines contain descriptions of the subsequent rows of the board. The description of one row consists of $n$ characters describing the consecutive fields in that row, where '#' denotes an obstacle, 'F' denotes a fort, and '.' denotes a free field. The field in row $1$ and column $1$ will always be described by 'Z', denoting Bajtazar's castle. The next $q$ lines contain descriptions of subsequent changes on the board. The $i$-th of them (for $1 \le i \le q$) contains two integers $x_i, y_i$ ($1 \le x_i, y_i \le n$) indicating that the field (which contains neither an obstacle nor Bajtazar's castle) in row $x_i$ and column $y_i$ changes its state between day $i$ and $i+1$: if there was a fort there, it is now gone (demolished), and if there was not, it is now there (built).

Output

Your program should output $q + 1$ lines. In the $i$-th of them (for $1 \le i \le q + 1$), you should output the minimum number of turns required to deliver messages to all forts on day $i$.

Examples

Input 1

4 3
Z...
###.
F.#F
...F
3 2
4 1
3 1

Output 1

10
10
11
10

Note 1

In the first query, we can deliver messages to all forts in 10 turns in the following way (columns denote consecutive turns):

Hero 1: $(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4) \to (4, 4) \to (4, 3) \to (4, 2) \to (3, 2) \to (3, 1)$ Hero 2: $(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4) \to (4, 4)$ Hero 3: $(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4)$

Subtasks