Description

Elephants are social animals, and for them, adjacent elephants are considered part of the same herd (diagonal adjacency does not count). In other words, if an elephant is located at coordinates (x, y), then the elephants at (x+1, y), (x-1, y), (x, y+1), and (x, y-1) belong to the same herd.

Given a map of size n*m, where # represents an elephant and . represents an empty space, the task is to determine the total number of herds.

Sample:

.#.#.
####.
##..#
....#
##.##

Input

The first line contains two integers, n and m.

1 ≤ n, m ≤ 1000

The following n lines each contain a string of length m, where each character is either # or ..

Output

Output the number of herds.

Note that you do NOT need to print '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After generating electricity in Japan, you board a plane to Singapore - this time stepping on an aircraft rather than a piezoelectric tile. It is raining outside, so you look outside the Window and see a large billboard running on Linux that says:

Singapore is turning rain into drinking water! Through the NEWater system, rainwater and used water are purified using advanced filtration and UV treatment. This ultra-clean water is then reused for industries and even drinking, helping Singapore reduce dependence on imported water. A smart solution for a water-scarce nation • turning rain into a reliable resource.

You are fascinated by the billboard’s ability to display and manage large amounts of text, so you decide to investigate how its underlying software works.

The system uses a very simple design for storing and editing text:

• A one-dimensional array of strings (effectively a 2D array of characters)

• A separate one-dimensional array len[], where each element stores the length of the corresponding string

Because the developer has not yet implemented null-terminated strings, the system does not rely on any special end-of-string character. Instead, the value in len[i] specifies exactly how many characters is in the i-th string. Any characters beyond this length should be ignored.

As new messages are displayed, the system processes a sequence of queries that modify the stored text.

However, the original source code has been lost. Your task is to reconstruct the missing program and accurately simulate the behavior of this system.

Constraints

• 1 <= n <= 100
• 1 <= q <= 1000
• All strings are initially empty

Input

The first line contains two integers:

N Q

• N — the number of strings

• Q — the number of queries

Each of the next Q lines describes one query in one of the following formats:

0 i c

Append the character c to the end of the i-th string.

1 i s

Append the string s to the end of the i-th string.

2

Print all strings in order from 0 to N-1.

Strings should be separated by newline characters when printed.

Line indices are 0-based.

Output

For every query of type 2, print all N strings.

Each string should appear on its own line.

Ignore the string if it is empty.

Each line should end with a newline.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss