E. Walrus Wallflowers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Many people know Walrus for a lot of things, for grinding math tests to singing Twice lyrics in his room. Speaking of Twice, he decided one day to plant a field of wallflowers in honor of the group. The field consists of an $$$n$$$ by $$$n$$$ grid. With so many flowers, Walrus needs to make sure he has the proper energy for watering them every day in the evening. The energy to water the entire grid is defined below.

  • Two cells are part of the same "budding" if both contain flowers, and the cells are adjacent or connected underground.
  • The amount of energy for watering a budding is defined as $$$\max(f - \sqrt{c}, 0)$$$, where $$$f$$$ is the number of cells with flowers, and $$$c$$$ is the number of underground connections that have at least one endpoint (flower cell) in the budding.
  • The energy to water the entire grid is the sum of the energies to water each budding.
Karp maintains the Walrus garden in the morning, and each day, Karp decides to either plant wallflowers at a cell, or connect two distinct cells underground. If Karp is planting flowers, the cell may already have flowers, in which case nothing happens. If Karp connects two cells, it is guaranteed that at least one of the two cells has flowers. It is possible that multiple connections exist between the same two cells.

After each day, help Walrus figure out how much energy he needs to use up!

Input

The first line will contain $$$n$$$ and $$$d$$$ ($$$2 \le n \le 100$$$ and $$$1 \le d \le 1000$$$): the size of the grid, and the number of days.

The next $$$n$$$ lines will contain binary strings of length $$$n$$$, where each character $$$s_i \in \{0, 1\}$$$ either means the cell is dirt ($$$0$$$) or has flowers ($$$1$$$).

The next $$$d$$$ lines will contain a query in the following format:

  • $$$1$$$ $$$x$$$ $$$y$$$ ($$$0 \le x,y \lt n$$$): Karp puts flowers at cell $$$(x, y)$$$ (row $$$x$$$, column $$$y$$$).
  • $$$2$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ ($$$0 \le x_1, y_1, x_2, y_2 \lt n$$$, $$$x_1 \ne x_2$$$ or $$$y_1 \ne y_2$$$): Karp connects cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ underground.
Output

For each of the $$$d$$$ queries, print out the amount of energy required. An absolute or relative error of at most $$$10^{-6}$$$ will be permitted.

Examples
Input
3 4
101
100
001
1 2 0
2 0 0 0 1
2 0 2 2 2
1 0 1
Output
5.00000000
4.00000000
3.00000000
4.58578644
Input
4 5
1011
1001
0010
1011
1 0 0
2 0 0 0 1
1 1 1
2 1 1 2 2
2 3 3 3 1
Output
9.00000000
8.00000000
9.00000000
8.58578644
8.26794919
Note

The below steps describe the first sample.

On the first day, Karp plants flowers at $$$(3, 1)$$$. The energy of the three buddings are $$$3$$$, $$$1$$$, and $$$1$$$.

On the second day, Karp connects $$$(1, 1)$$$ with $$$(1, 2)$$$. The energy of the three buddings are $$$3 - \sqrt{1}$$$, $$$1$$$, and $$$1$$$.

On the third day, Karp connects $$$(1, 3)$$$ with $$$(3, 3)$$$. The energy of the two buddings are $$$3 - \sqrt{1}$$$ and $$$2 - \sqrt{1}$$$.

On the fourth day, Karp plants flowers at $$$(1, 2$$$). The energy of the only budding is $$$6 - \sqrt{2}$$$.