Tram Seat Conflict Explosion

In a tram there is always chaos when people fight for seats. In our problem, the tram is represented as an R×C grid. Each cell is either a floor (denoted by a .), a passenger (denoted by X), or a seat (denoted by L).

Every round, each remaining passenger quickly targets the seat that is closest to him/her. The distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is defined by the Euclidean distance, i.e. \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\). In case there are multiple seats with the same minimal distance for a passenger, the passenger will choose the one with the smallest row number; if still tied, then the one with the smallest column number.

After all passengers have chosen their target seats for the round, the following happens simultaneously for each seat:

• If the seat is targeted by exactly one passenger then that passenger sits there and both the seat and the passenger are removed from further rounds.
• If the seat is targeted by more than one passenger, then we look at the computed distances. Let \(d_{min}\) be the minimum distance among the targeting passengers.
  
  • If exactly one passenger achieves \(d_{min}\), then that passenger gets the seat (and both are removed), while the others will try again in subsequent rounds.
  • If two or more passengers achieve \(d_{min}\) (i.e. there is a tie for the closest), an explosion event occurs at that seat. In an explosion event, the seat and all passengers targeting it are removed from further rounds, and the explosion is counted.

The rounds are executed repeatedly. The process terminates when either no passengers remain or no seats remain. Your task is to simulate the process round by round and output the total number of explosion events that occur before the termination round. (Note that if an explosion event happens in the round that causes termination, those explosions are included in the total count.)

Important: In each round all assignments and explosions are processed simultaneously. Each passenger chooses his/her target based on the current positions of passengers and seats.

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 100), representing the number of rows and columns in the grid. Each of the next R lines contains a string of length C composed only of characters '.', 'X', and 'L', representing the floor, a passenger, and a seat respectively.

outputFormat

Output a single integer — the total number of explosion events that occur during the simulation.

sample

3 3
...
.X.
..L

0