Om Nom really likes candies and doesn't like spiders as they frequently steal candies.…
- User
Om Nom really likes candies and doesn't like spiders as they frequently steal candies. One day Om Nom fancied a walk in a park. Unfortunately, the park has some spiders and Om Nom doesn't want to see them at all.
The park can be represented as a rectangular n × m field. The park has k spiders, each spider at time 0 is at some cell of the field. The spiders move all the time, and each spider always moves in one of the four directions (left, right, down, up). In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. If there is no cell in the given direction, then the spider leaves the park. The spiders do not interfere with each other as they move. Specifically, one cell can have multiple spiders at the same time.
Om Nom isn't yet sure where to start his walk from but he definitely wants:
- to start walking at time 0 at an upper row cell of the field (it is guaranteed that the cells in this row do not contain any spiders);
- to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park).
We know that Om Nom moves by jumping. One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries.
Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time. Om Nom wants to choose the optimal cell to start the walk from. That's why he wonders: for each possible starting cell, how many spiders will he see during the walk if he starts from this cell? Help him and calculate the required value for each possible starting cell. Input
The first line contains three integers n, m, k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1)).
Each of the next n lines contains m characters — the description of the park. The characters in the i-th line describe the i-th row of the park field. If the character in the line equals ".", that means that the corresponding cell of the field is empty; otherwise, the character in the line will equal one of the four characters: "L" (meaning that this cell has a spider at time 0, moving left), "R" (a spider moving right), "U" (a spider moving up), "D" (a spider moving down).
It is guaranteed that the first row doesn't contain any spiders. It is guaranteed that the description of the field contains no extra characters. It is guaranteed that at time 0 the field contains exactly k spiders.
Output
Print m integers: the j-th integer must show the number of spiders Om Nom will see if he starts his walk from the j-th cell of the first row. The cells in any row of the field are numbered from left to right.
Examples
Input
3 3 4 ... R.L R.U
Output
0 2 2
Input
2 2 2 .. RL
Output
1 1
Input
2 2 2 .. LR
Output
0 0
Input
3 4 8 .... RRLL UUUU
Output
1 3 3 1
Input
2 2 2 .. UU
Output
0 0
Note
Consider the first sample. The notes below show how the spider arrangement changes on the field over time:
... ... ..U ... R.L -> .*U -> L.R -> ... R.U .R. ..R ...Character "*" represents a cell that contains two spiders at the same time.
- If Om Nom starts from the first cell of the first row, he won't see any spiders.
- If he starts from the second cell, he will see two spiders at time 1.
- If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 2.
Assistant
We need to parse the problem carefully.
We have an n x m grid, rows 1 to n (top to bottom). At time 0, we have k spiders at some cells (given by letters L,R,U,D). The spiders move each unit time in their specified direction: L = left, R = right, U = up, D = down. If they go outside the grid, they leave and presumably vanish. They do not interact. They can occupy same cell.
Om Nom starts at time 0 at a cell in the first row (row 1). He will move downward by jumping: each jump takes 1 time unit, and he moves from his current cell to a side-adjacent cell on the lower row (i.e., row+1) or outside the park. More precisely: "One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries." So in each step, from his current cell (i, j) at time t, he will jump to (i+1, j') where j' is either j-1, j, or j+1? Actually "side-adjacent cell on the lower row" means down-left or down-right? Or also directly below? Usually in such problems, side-adjacent includes directly below? But "side-adjacent" typically means adjacent by side, i.e., sharing a side, which includes up, down, left, right. But the phrase "side-adjacent cell on the lower row" could be interpreted as: the cell is on the lower row and is side-adjacent to his current cell. The lower row is row i+1. The cells on that row that are side-adjacent to (i, j) are (i+1, j) (directly below, sharing a vertical side) and (i+1, j-1) and (i+1, j+1) if those exist? But are those side-adjacent? (i+1, j-1) shares a corner, not a side. So it is not side-adjacent; it is diagonally adjacent. Usually "side-adjacent" means adjacent via a side (not diagonal). So then only (i+1, j) is side-adjacent because they share a side? Actually (i, j) and (i+1, j) share a side (the bottom side of (i,j) and top side of (i+1,j)). Yes. (i+1, j-1) shares only a corner. So not side-adjacent. So the jump moves to the cell directly below? But then why mention "or outside the park boundaries"? When moving down, if there is no cell directly below (i.e., i = n), then he can leave. But then what about left/right? Possibly he can move down-left or down-right? Let's read: "One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries." It says side-adjacent cell on the lower row. The lower row is i+1. So the cell on that row that is side-adjacent to his current cell could be the one directly below. That's the only cell on row i+1 that shares a side. But maybe they consider also left and right? Actually a cell on the lower row can be side-adjacent if we consider the adjacency to his cell? For a cell (i, j), which cells on row i+1 are side-adjacent? The side-adjacent cells to (i,j) are (i-1,j) (up), (i+1,j) (down), (i,j-1) (left), (i,j+1) (right). Only one of these is on the lower row: (i+1, j). So indeed only directly below.
But perhaps they meant "side-adjacent" in the sense that the cell is adjacent to the side of his current cell, meaning he can jump diagonally? Let's check typical phrasing: In many problems, "side-adjacent" is used to distinguish from "corner-adjacent". So yes, side-adjacent means sharing a side. So only directly below.
But wait, then the problem becomes: Om Nom starts at row1, column c. At each time step, he moves down one row (i.e., row+1) staying in same column? That would be just a straight downward path. But then the start column matters only for which column he's in, and he will always go down the same column. But then why would they talk about "walk by moving down the field towards the lowest row"? And "jump transports from his cell to either a side-adjacent cell on the lower row or outside the park boundaries." The phrase "either" suggests two possibilities: either to a side-adjacent cell on the lower row, or outside. So it's like: you can either jump to the cell below (if exists) or jump outside (i.e., leave). But you could also possibly jump left/right? That seems too trivial. However, the sample outputs indicate more interesting behavior.
Let's test sample 1: n=3,m=3. Rows: 1: ... 2: R.L 3: R.U
Interpretation: Row2: columns: col1: R, col2: ., col3: L? Actually "R.L" likely means R . L? Yes, characters: 'R', '.', 'L'. Row3: 'R', '.', 'U'.
Spiders: At time0, positions: (2,1) moving right; (2,3) moving left; (3,1) moving right; (3,3) moving up.
Now, compute number of spiders seen if Om Nom starts at column 1,2,3 of row1.
If Om Nom just moves straight down column j (i.e., jumps to (2,j) at time1, then (3,j) at time2, then leaves at time3 maybe). At time t when he lands on cell (i,j) he sees spiders that are at that cell at that time.
We need to compute for each start column: how many spiders he sees (counting multiple spiders possibly same cell at same time). Let's simulate manually according to that assumption.
Spiders move each time step. Let's compute positions at times 0,1,2,... (maybe up to 3). At time0: row2 col1 R, row2 col3 L, row3 col1 R, row3 col3 U.
We track each spider's movement.
Spider A: (2,1) moving right. So at time1: moves to (2,2). At time2: moves to (2,3). At time3: moves to (2,4) which is outside (since m=3), so leaves. So it's in the park at times0-2.
Spider B: (2,3) moving left. At time1: (2,2). At time2: (2,1). At time3: (2,0) outside. So times0-2.
Spider C: (3,1) moving right. At time1: (3,2). At time2: (3,3). At time3: (3,4) outside. Times0-2.
Spider D: (3,3) moving up. At time1: (2,3). At time2: (1,3). At time3: (0,3) outside. But note: row1 is top row. There is no spider initially on row1, but it can move into row1. At time2, it's at (1,3). That is allowed. So times0-2.
Now, Om Nom:
He starts at time0 at (1,j). He "lands" at that cell at time0? The problem says: "Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time." Does he also see spiders at start? He lands at the start cell at time0 (I think so, as he starts walking at time0 at that cell). So we need to consider if he sees spiders at time0 at his start cell. But it's guaranteed that first row has no spiders at time0, so at time0 start cell is safe (no spiders). So we consider his entire walk: he starts at row1 at time0, then at time1 jumps to row2, etc. He might also leave after row n? After row n (last row), the next jump would go outside. But does he land on row n? Yes, he will land on row n at time n-1 (if n rows). Then at time n, he jumps outside, and presumably does not land on any cell, so no more sightings. So we need to consider times t=0,1,..., n-1 for rows 1 to n.
Now, if he moves straight down (same column), then his path: (1,j) at t=0, (2,j) at t=1, (3,j) at t=2 (since n=3), then at t=3 he jumps outside (no cell). So we need to compute spiders at those positions at those times.
Compute for j=1 (col1): t=0: (1,1) no spiders (since first row no spiders initially, but spider might arrive later? At time0, no spider). So see 0. t=1: (2,1) at time1. Spiders present at (2,1) at time1: From above: Spider A was at (2,1) at time0 but moved to (2,2) at time1, so not there. Spider B: at time1 is at (2,2). Spider C: at time1 (3,2). Spider D: at time1 (2,3). So none at (2,1). So see 0. t=2: (3,1) at time2. Spiders: Spider A: (2,3); B: (2,1); C: (3,3); D: (1,3). None at (3,1). So see 0. Total = 0. Output first sample says "0 2 2", so for col1 expected 0 matches. Good.
Now col2: Path: (1,2) t0, (2,2) t1, (3,2) t2. t0: (1,2) no spiders -> 0. t1: (2,2) at t1. Spiders: A at (2,2), B at (2,2) (both moved to (2,2) at time1). Also C at (3,2), D at (2,3). So (2,2) has A and B => 2 spiders. So see 2. t2: (3,2) at t2. Spiders: A: (2,3), B: (2,1), C: (3,3), D: (1,3). None at (3,2). So see 0. Total 2. Output for col2 is 2. That matches.
Now col3: Path: (1,3) t0, (2,3) t1, (3,3) t2. t0: (1,3) no spiders (but spider D will be at (1,3) at t2, not t0). So 0. t1: (2,3) at t1. Spiders: A at (2,2)? Actually A at t1 is (2,2). B at (2,2). C at (3,2). D at (2,3). So only D at (2,3) => 1 spider? But expected total for col3 is 2. Let's check. t1: (2,3) has D. So see 1. t2: (3,3) at t2. Spiders: A at (2,3)?? Wait A at t2 is (2,3) (since right moves to col3 at t2). Actually A: (2,1) t0, (2,2) t1, (2,3) t2. B: (2,3) t0, (2,2) t1, (2,1) t2. C: (3,1) t0, (3,2) t1, (3,3) t2. D: (3,3) t0, (2,3) t1, (1,3) t2. So at t2: (3,3) has spider C? Yes C is at (3,3). Also possibly others? A at (2,3), B at (2,1), D at (1,3). So (3,3) has 1 spider (C). So that would be 1. Total = 2 (1+1) matches expected 2. So indeed col3 sees 2 spiders: one at time1 (D) and one at time2 (C). Wait but earlier I said at t1 (2,3) has D, yes. At t2 (3,3) has C. So total 2. That matches output.
Thus, the assumption that Om Nom moves straight down the same column is consistent with sample 1.
Let's test sample 2: n=2, m=2, k=2. Rows: 1: .. 2: RL So spiders: row2 col1: R (right), row2 col2: L (left). Compute spider movements: Spider R: (2,1) at t0, moves right -> at t1: (2,2). At t2: would leave (2,3) out. Spider L: (2,2) at t0, moves left -> at t1: (2,1). At t2: (2,0) out.
Om Nom starts at row1 col? at t0. Then at t1 jumps to row2 (since n=2). After that at t2 jumps out, no further.
Paths: col1: (1,1) t0, (2,1) t1. col2: (1,2) t0, (2,2) t1.
Compute sightings: col1: t0: (1,1) empty; t1: (2,1) at t1: which spiders? At t1: Spider R at (2,2), Spider L at (2,1). So (2,1) has L => 1 spider. Total = 1. Expected output: "1 1". col1: 1, col2: 1.
Check col2: t1: (2,2) at t1: R is there => 1. So matches.
Sample 3: n=2,m=2,k=2. Rows: 1: .. 2: LR Spiders: row2 col1: L (left), row2 col2: R (right). Movements: L at (2,1) moves left -> at t1: (2,0) out, so only present at t0. R at (2,2) moves right -> at t1: (2,3) out, present at t0. Om Nom: col1: (1,1) t0, (2,1) t1. At t1, (2,1): no spider (L left at t0, at t1 gone). So total 0. col2: (2,2) t1: no spider (R gone). So 0. Output: 0 0 matches.
Sample 4: n=3, m=4, k=8. Rows: 1: .... 2: RRLL 3: UUUU Spiders: row2: col1 R, col2 R, col3 L, col4 L? Actually "RRLL" => positions (2,1):R, (2,2):R, (2,3):L, (2,4):L. Row3: "UUUU" => all 4 columns have U (up).
Total spiders: 8.
Compute expected output: 1 3 3 1.
We'll test with straight-down assumption.
First, compute spider trajectories.
We have 4 spiders on row2: R,R,L,L. And 4 on row3: all U.
Let's index columns 1..4.
Row2 spiders:
- R1 at (2,1): moves right: positions over time: t0 (2,1); t1 (2,2); t2 (2,3); t3 (2,4); t4 (2,5) out. So present t0-3.
- R2 at (2,2): t0 (2,2); t1 (2,3); t2 (2,4); t3 (2,5) out; present t0-2.
- L3 at (2,3): moves left: t0 (2,3); t1 (2,2); t2 (2,1); t3 (2,0) out; present t0-2.
- L4 at (2,4): t0 (2,4); t1 (2,3); t2 (2,2); t3 (2,1); t4 (2,0) out? Wait careful: from col4 left: t1 col3, t2 col2, t3 col1, t4 col0 out. So present t0-3 (since at t3 still col1). Actually at t3 (2,1) inside; at t4 out.
Row3 spiders (all U):
- U5 at (3,1): moves up: t0 (3,1); t1 (2,1); t2 (1,1); t3 (0,1) out; present t0-2.
- U6 at (3,2): t0 (3,2); t1 (2,2); t2 (1,2); t3 out; present t0-2.
- U7 at (3,3): t0 (3,3); t1 (2,3); t2 (1,3); t3 out; present t0-2.
- U8 at (3,4): t0 (3,4); t1 (2,4); t2 (1,4); t3 out; present t0-2.
Now Om Nom's walk: start at row1 col j at t0; row2 at t1; row3 at t2; then leave.
We need total spiders seen at (1,j) t0, (2,j) t1, (3,j) t2. Since row1 initially no spiders, but spiders can move into row1 at t2 (the U spiders). So we must consider t0, t1, t2.
Compute for each column j=1..4.
We'll collect all spiders that are at (1,j) at t0? t0 only initial, but first row has no spiders, so 0. Also (1,j) at t0, spiders may move into row1 at t2 but not t0. So t0 always 0.
Now (2,j) at t1. We need to list which spiders are at column j at time 1.
Time1 positions:
- R1: (2,2)
- R2: (2,3)
- L3: (2,2)
- L4: (2,3)
- U5: (2,1)
- U6: (2,2)
- U7: (2,3)
- U8: (2,4)
Let's list per column:
col1 at t1: U5 at (2,1). Also any others? R's, L's? L4 at t1? L4 is at (2,3). L3 at (2,2). R1 (2,2). R2 (2,3). So only U5. So count=1.
col2 at t1: R1 (2,2), L3 (2,2), U6 (2,2). That's three. Also maybe others? R2 at col3, L4 col3, U7 col3, U8 col4. So col2 count=3.
col3 at t1: R2 (2,3), L4 (2,3), U7 (2,3). That's 3. Also maybe others? R1 col2, L3 col2, U6 col2, U5 col1, U8 col4. So col3 count=3.
col4 at t1: U8 (2,4). Possibly L4? L4 is col3. R2 col3. So col4 count=1.
Now (3,j) at t2. Compute all spiders at time2 positions:
- R1: (2,3) (since t2: from (2,1) -> (2,2) t1 -> (2,3) t2)
- R2: (2,4) (t2)
- L3: (2,1) (t2)
- L4: (2,2) (t2)
- U5: (1,1) (t2)
- U6: (1,2) (t2)
- U7: (1,3) (t2)
- U8: (1,4) (t2)
Also note: Spiders from row2 may be at row3? No, they stay on row2 because they move left/right, not vertical. So at t2, row3 has no spiders? Actually row3 initially had U's, but they moved up, so at t2 they are at row1. So row3 is empty at t2. So (3,j) at t2: none? Let's verify if any spider could be at row3 at t2. R's and L's only move horizontally, so they stay on row2. U's move up, so they go to row2 then row1. D's none. So indeed row3 is empty at t2. So count for (3,j) is 0 for all j.
Thus total sightings per column: col1: t0 0 + t1 1 + t2 0 = 1 col2: 0 + 3 + 0 = 3 col3: 0 + 3 + 0 = 3 col4: 0 + 1 + 0 = 1
Matches sample output: 1 3 3 1.
So straight-down assumption works.
Sample 5: n=2,m=2,k=2 Rows: 1: .. 2: UU Spiders: row2 both columns: U (up). Movements: U at (2,1): t0 (2,1); t1 (1,1); t2 (0,1) out. U at (2,2): t0 (2,2); t1 (1,2); t2 out.
Om Nom: col1: (1,1) t0, (2,1) t1. col2: (1,2) t0, (2,2) t1. t0: row1 empty (initial). But note: at t0, spider are at row2, so (1,1) no spider. t1: (2,1) at t1: spider from (2,1) moved up to (1,1) at t1, so (2,1) at t1 has no spider? Actually spider moves: at t1, the spider from (2,1) is at (1,1). So (2,1) is empty. Similarly for col2. So total 0 each. Output "0 0" matches.
Thus, the problem reduces to: For each starting column j (1-indexed), Om Nom visits cells: (1,j) at time0, (2,j) at time1, ..., (n,j) at time n-1. He sees spiders that are exactly at that cell at that time.
We need to compute for each column j, the sum over rows i=1..n of the number of spiders that are at (i, j) at time t = i-1 (since time from 0). Because he starts at row1 at time0.
Now, we have k spiders, each with a starting position (r0, c0) and a direction d (L,R,U,D). They move deterministically: at time t, a spider's position is (r_t, c_t) where r_t and c_t depend on direction and initial position, and if it goes out of bounds, it disappears. So we need to count, for each (i, j) and time t = i-1, whether a given spider is at (i, j) at that time.
We can reframe: For each spider, we can compute the times at which it will be at each row and column? But more efficiently, we can simulate contributions to the sum for each column.
Given constraints: n,m up to 2000, so nm up to 4e6. k up to m(n-1) (since first row no spiders). That's up to about 4e6 as well. So we need O(n*m) or O((n+m)*something) solution.
We need to compute answer for each column j.
Observation: The time when Om Nom visits (i, j) is t = i-1.
So for a spider, its position at time t: (r0 + drdirection_t, c0 + dcdirection_t) for U/D or L/R. But careful: Spiders move constantly in one direction. So position at time t: if direction is L: (r0, c0 - t); if R: (r0, c0 + t); if U: (r0 - t, c0); if D: (r0 + t, c0). Provided they stay within bounds, else they disappear. They can also move out of bounds at some time t_exit, after which they are not present.
We need to count, for each column j, the number of spiders such that there exists i (1..n) with t=i-1, and (i,j) equals spider's position at time t, and t is within its lifespan.
Alternatively, think per spider: For each spider, determine all (i, j, t = i-1) where it is present. Then add 1 to answer[j] for that i if j matches and t matches? Actually each spider contributes to the total sightings count for a given starting column j if there exists a row i such that at time i-1 the spider is at (i, j). But note that each spider might be seen at most once? Actually it could be seen multiple times if Om Nom passes through cells where the spider appears at different times? But Om Nom visits exactly one cell per time step. However, a spider could be at different cells at different times. Could Om Nom see the same spider more than once? Yes, if the spider's path intersects Om Nom's path at multiple times? But Om Nom's path is a vertical column: fixed column j, rows 1..n at times 0..n-1. The spider moves, potentially crossing that column at multiple times. But note: Om Nom only lands on cells at specific times: row i at time i-1. So the spider could be at (i, j) at time i-1 for multiple i. That would cause the same spider to be seen multiple times. Is that possible? Let's think.
If spider moves horizontally (L/R), its row remains constant (r0). So it could be at column j at time t if c0 ± t = j. For Om Nom to see it at row i, we need i = r0 (since row constant) and t = i-1 = r0-1. So the spider would be seen only if c0 ± (r0-1) = j. So it contributes at most once (since only at row r0). So horizontal spiders can be seen at most once.
Vertical spiders (U/D): column constant c0, row changes: r0 ∓ t (U: r0 - t, D: r0 + t). Om Nom visits row i at time i-1. So intersection occurs when i = r0 ∓ (i-1) => solve: For U: i = r0 - (i-1) => i = r0 - i + 1 => 2i = r0 + 1 => i = (r0+1)/2. For D: i = r0 + (i-1) => i = r0 + i - 1 => 1 = r0 - 1? That gives nonsense. Let's do properly: At time t = i-1, spider U is at row r0 - (i-1). For Om Nom to be at that cell, we need i = r0 - (i-1) => i = r0 - i + 1 => 2i = r0 + 1 => i = (r0+1)/2. This must be integer and within 1..n. So at most one possible row i for a U spider. Similarly, D: i = r0 + (i-1) => i = r0 + i - 1 => 0 = r0 - 1 => r0 = 1. But r0 cannot be 1 because first row has no spiders. Actually D could start at row >=2. So i = r0 + (i-1) implies 1 = r0? No, it's impossible unless we cancel i: subtract i: 0 = r0 - 1 => r0 = 1. So no solution for D spiders unless r0=1 (which is prohibited). But wait, D spiders move down, so row increases. Om Nom moves down from row1. At time t, Om Nom is at row 1+t. D spider is at row r0 + t. They could coincide if 1+t = r0 + t => 1 = r0 => r0=1. So indeed only if D starts at row1 which doesn't happen. So D spiders are never seen by Om Nom? Let's check sample 1: there was a spider D? Actually sample 1 had spiders: two R, one L, one U. No D. So D spiders would not intersect the straight-down path? But wait, what about spider D in other samples? None. But is it possible that a D spider could be seen? If Om Nom starts at some column, he goes down rows 1,2,...,n. D spider starts at some row >1 and moves down. At time t, Om Nom at row 1+t, D at row r0 + t. For them to meet at same cell, we need same row and column. Column: D stays at constant column c0. So they must have same column j = c0. Row equality: 1+t = r0 + t => 1 = r0. So impossible. So D spiders are never seen! That is an interesting observation. Similarly, U spiders can be seen at most once (if (r0+1) even). So each spider contributes at most once to a given column j.
Thus overall, each spider contributes to exactly one starting column j (if at all) at a specific time. However, could a spider be seen from multiple starting columns? Since each starting column is a different path, a spider may be seen from at most one column? Actually a spider could potentially be seen from multiple columns if its movement crosses different columns at the times Om Nom is at those rows. But note: For a given spider, its intersection with Om Nom's path depends on column j and row i. The spider's row and column are functions of time. For a fixed column j, we check if there exists i such that (i, j) equals spider's position at time i-1. If we consider different j, we get different conditions. So a spider might satisfy that condition for more than one j? Let's test with a horizontal spider (L/R). Condition: row i = r0, t = i-1 = r0-1, column j = c0 ± (r0-1). So j is uniquely determined: j = c0 + (r0-1) if R, or j = c0 - (r0-1) if L. So it can only be seen from that one column, provided that j is within [1,m]. So horizontal spiders contribute to at most one column.
For vertical spiders (U). Condition: column constant c0, and row i must satisfy i = r0 - (i-1) => i = (r0+1)/2, so i determined uniquely (if integer). Then t = i-1, and spider's column is c0. So then j must be c0. So it contributes to column c0 only, if i is integer and within 1..n. So also at most one column.
For D spiders: never. So indeed each spider that is seen at all will be seen exactly once for exactly one starting column (the column of the intersection). Thus the answer for each column j is simply the number of spiders that intersect Om Nom's path when starting at column j.
Hence we need to compute for each column j, count of spiders that satisfy the meeting condition.
Now we have up to 4e6 spiders, and n,m up to 2000. We can compute per spider its contribution directly: for each spider, if it will be seen from some column j, increment ans[j]. Then output ans[1..m]. The challenge is to compute quickly: for each spider, determine if and which column j it contributes to, and do it efficiently.
Let's formalize meeting condition.
Spider type L: starts at (r0, c0). Moves left each step: at time t, position = (r0, c0 - t). It is present for t = 0,1,..., until c0 - t < 1 or > m? Actually left: exit when c0 - t < 1 => t >= c0. So lifespan t in [0, c0-1] (since when t = c0, column becomes 0, out). But we only care about times up to n-1 (since Om Nom's last time is n-1). Om Nom visits row i = t+1 at time t. So for spider to be seen, we need:
- Row matches: i = r0.
- Time matches: t = i-1 = r0 -1.
- So we need t = r0 - 1.
- Also, at that time, spider must be within bounds: that is, c0 - t must be between 1 and m.
- Then the column j = c0 - t.
Thus condition: r0 - 1 <= c0 - 1? Actually t = r0 -1. So condition for existence: r0 - 1 <= c0 - 1? Wait we need c0 - (r0 - 1) >= 1 => c0 >= r0. Also need <= m: c0 - (r0 - 1) <= m, which is typically true if c0 <= m, but since c0 - (r0-1) <= c0, and c0 <= m, it's fine. But also need that spider hasn't left before that time: spider is present at time t if t <= c0 - 1 (since exit when t >= c0). So t = r0 - 1 must be <= c0 - 1 => r0 - 1 <= c0 - 1 => r0 <= c0. So condition: r0 <= c0. Also t must be >=0 obviously. So for L spider, it contributes to column j = c0 - (r0 - 1) if r0 <= c0. (Also note that row must be within 1..n, but r0 is given to be between 2..n because row1 no spiders; also r0 <= n, okay.)
Similarly, R spider: position (r0, c0 + t). Exit when c0 + t > m => t >= m - c0 + 1. So lifespan t in [0, m-c0] (since when t = m-c0+1, column m+1 out). Condition:
- Row i = r0, t = r0 -1.
- Need t <= m - c0 => r0 - 1 <= m - c0 => r0 <= m - c0 + 1? Wait rearrange: r0 - 1 <= m - c0 => r0 <= m - c0 + 1.
- Also need j = c0 + t = c0 + (r0 - 1) between 1..m, which holds if above condition ensures j <= m? Actually j = c0 + r0 - 1, and condition r0 - 1 <= m - c0 gives j <= m. Also need j >=1 (obviously since c0 >=1 and r0>=2). So condition: r0 <= m - c0 + 1? Actually check: r0 <= m - c0 + 1. That is equivalent to c0 + r0 - 1 <= m, which is exactly j <= m. Also need t >=0 and spider present at that time (which is given by that). So condition: c0 + r0 - 1 <= m. Also need that row r0 exists (it does). So R spider contributes to column j = c0 + r0 - 1 if c0 + r0 - 1 <= m.
Now for U spider: starts at (r0, c0). Moves up: position (r0 - t, c0). Exit when r0 - t < 1 => t >= r0. So lifespan t in [0, r0-1]. Condition for meeting:
- At time t, Om Nom is at row i = t+1. We need that row equals spider's row: i = r0 - t => t+1 = r0 - t => 2t = r0 - 1 => t = (r0 - 1)/2.
- t must be integer, i.e., r0 - 1 must be even => r0 odd? Actually r0 -1 even => r0 odd? If r0 is odd, r0-1 is even, so t integer. More precisely, need (r0-1) % 2 == 0 => r0 odd.
- Also t must be within lifespan: t <= r0-1, but if t = (r0-1)/2, it's <= r0-1 for r0>=1, so okay.
- Then row i = t+1 = (r0+1)/2, which must be within 1..n (it will be since r0 <= n, (r0+1)/2 <= n for n>=2? Possibly but need check: (r0+1)/2 <= n, which holds if r0 <= 2n-1, but r0 <= n, so fine). Also i >=1 obviously.
- Column: j = c0.
- Also need that at time t, spider hasn't left: t <= r0-1, which holds because t = (r0-1)/2 <= r0-1 for r0>=1.
- Also need that spider hasn't left before that time? It stays until t = r0-1 inclusive? Actually exit when r0 - t < 1 => t >= r0, so at t = r0-1, row=1, still inside. So t = (r0-1)/2 is fine.
- Also note: row i = (r0+1)/2 should be integer; since r0 odd, (r0+1)/2 integer.
Thus U spider contributes to column j = c0 if r0 is odd.
Wait, also need that Om Nom visits row i = (r0+1)/2 at time t = i-1. That is natural. Also we need to ensure that at that time, spider is still in the park: it is at row i. But we need to check that spider has not left due to column boundary? Column constant, so okay.
But what about the possibility that spider might have left because it moves up and maybe row i >? Actually we already accounted.
Thus for U spider: condition: r0 is odd. Then it contributes to column c0.
But we also need to ensure that the meeting row i is within 1..n. Since r0 <= n, and r0 odd, i = (r0+1)/2 is at most (n+1)/2 which is <= n for n>=1. Actually if r0 = n and n is odd, i = (n+1)/2 which is <= n. So okay.
But what if n is small? Eg, n=2, r0=2 (even) so no contribution; r0=2 even, condition false. So ok.
Now for D spider: we argued never meets because equation yields r0=1 impossible. So D spiders contribute nothing.
Thus answer per column j = number of L spiders with r0 <= c0 and j = c0 - (r0 - 1) + number of R spiders with c0 + r0 - 1 <= m and j = c0 + r0 - 1 + number of U spiders with r0 odd and j = c0.
We also need to consider that spiders might be seen at times beyond n-1? Om Nom's walk stops after row n at time n-1. He does not go beyond. So we also must ensure that the meeting row i (the row of intersection) is within 1..n. For L and R, i = r0, which is given to be between 2..n, so automatically i<=n. For U, i = (r0+1)/2; need to ensure i <= n. Since r0 <= n, (r0+1)/2 <= (n+1)/2 <= n for n>=1. Yes, always. But also need i >= 1, which is true. So no extra condition.
Also check that for L and R, the meeting time t = r0-1 must be less than or equal to the spider's lifespan. For L: we need t <= c0-1 (since exit when column becomes 0). That gave r0 <= c0. For R: t <= m - c0, giving c0 + r0 - 1 <= m. Good.
But also, what about the case where the spider might have left due to row boundary? L and R only move horizontally, so they stay on row r0. Row boundaries are fixed: if they go out horizontally, they leave. They never leave due to row. So no row condition.
Now, we also need to consider that some spiders could be at the same cell at the same time as Om Nom at time 0? But row1 has no spiders initially, so that's fine.
Thus we can compute answer by iterating over all spiders and increment the appropriate column if condition satisfied.
Given n,m up to 2000, and k up to m*(n-1) ~ 4e6, which is maybe up to 4 million. That's manageable if we just iterate over all spiders and do O(1) per spider. But reading input: we have an n x m grid of characters. So total cells up to 4e6, which is fine. We can parse each cell, if it's a spider (one of L,R,U,D), we treat accordingly.
Thus algorithm:
Initialize ans[1..m] = 0.
For each cell (i, j) (1-indexed) from row 1 to n, col 1 to m, read char ch. If ch == 'L': if i <= j: // condition r0 <= c0 col = j - (i - 1) // j - (r0-1) ans[col] += 1 If ch == 'R': if j + i - 1 <= m: // c0 + r0 -1 <= m col = j + i - 1 ans[col] += 1 If ch == 'U': if i % 2 == 1: // r0 odd col = j ans[col] += 1 If ch == 'D': // no contribution If ch == '.' : ignore.
After processing all spiders, output ans[1..m] separated by spaces.
Double-check with samples.
Sample 1: Row2 col1: L? Actually row2 col1 is R, so R. i=2, j=1: check j+i-1 = 1+2-1=2 <=3 -> col=2. ans[2]++. Row2 col3: L? row2 col3 is L: i=2, j=3: check i<=j? 2<=3 true -> col = 3 - (2-1) = 2. ans[2]++. Row3 col1: R: i=3, j=1: j+i-1=1+3-1=3 <=3 -> col=3. ans[3]++. Row3 col3: U: i=3, j=3: i odd? 3 odd true -> ans[3]++. So ans[1]=0, ans[2]=2, ans[3]=2. Matches.
Sample 2: Row2 col1: R: i=2,j=1 -> col=1+2-1=2 <=2? Yes, col=2, ans[2]++. Row2 col2: L: i=2,j=2 -> i<=j? 2<=2 true -> col=2-(2-1)=1, ans[1]++. So ans[1]=1, ans[2]=1. Good.
Sample 3: Row2 col1: L: i=2,j=1: i<=j? 2<=1 false -> no. Row2 col2: R: i=2,j=2: col=2+2-1=3 >2 -> no. So ans[1]=0, ans[2]=0. Good.
Sample 4: We have many spiders. Compute: Row2: col1 R: i=2,j=1: col = 1+2-1=2 <=4 -> ans[2]++. col2 R: i=2,j=2: col = 2+2-1=3 -> ans[3]++. col3 L: i=2,j=3: i<=j? 2<=3 true -> col=3-(2-1)=2 -> ans[2]++. col4 L: i=2,j=4: i<=j? 2<=4 true -> col=4-(2-1)=3 -> ans[3]++. Row3 (all U): col1 U: i=3,j=1: i odd? 3 odd true -> ans[1]++. col2 U: i=3,j=2: odd -> ans[2]++. col3 U: i=3,j=3: -> ans[3]++. col4 U: i=3,j=4: -> ans[4]++. Now total: ans[1]=1, ans[2]= (R from (2,1):1, L from (2,3):1, U from (3,2):1) =3, ans[3]= (R from (2,2):1, L from (2,4):1, U from (3,3):1) =3, ans[4]=1. Matches.
Sample 5: Row2 col1 U: i=2,j=1: i odd? 2 even -> no. Row2 col2 U: i=2,j=2: even -> no. So ans all 0. Matches.
So solution is simple.
But is there any nuance? Wait, check condition for L spider: we used i <= j. But is it exactly r0 <= c0? Let's re-derive to be sure.
L spider: at time t = r0 - 1, column = c0 - (r0 - 1). Must be >= 1, i.e., c0 - (r0 - 1) >= 1 -> c0 >= r0. Also must be <= m, which is automatic since c0 <= m and subtracting positive? Could be less than 1 only. Also need that spider hasn't left before that time: it leaves when column < 1, i.e., at time t >= c0. So we need t = r0-1 < c0? Actually it's present if t <= c0-1, so r0-1 <= c0-1 -> r0 <= c0. So condition is r0 <= c0. Good.
But also we need to ensure that at time t, spider is still in the park: the row is r0, which is within 1..n. Row is fine.
Now, consider L spider where c0 - (r0 - 1) might be > m? That would be impossible because c0 <= m and we subtract positive, so result <= m. So fine.
Thus condition is exactly r0 <= c0.
Similarly, R: condition c0 + r0 - 1 <= m.
U: condition r0 odd, as derived from t integer. Also need that the spider is still present at that time: it leaves when r0 - t < 1 => t >= r0. At t = (r0-1)/2, t < r0 for r0>1, so present. Good.
But what about U spider where r0 = 1? Row1 has no spiders, so no U spider in row1. So r0 >=2. So fine.
Now, is there any possibility that a spider could be seen at a time when Om Nom is outside the park? No, because Om Nom visits rows 1..n and then leaves. Only rows 1..n.
Edge cases: n=2,m=2. Already covered.
What about D spiders? Could they be seen if Om Nom's path is not strictly straight down? But the problem statement says: "walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park)." and "One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries." This phrasing might allow moving to a cell on the lower row that is side-adjacent, which could be left or right? Actually we interpreted side-adjacent as directly below, but maybe "side-adjacent cell on the lower row" means a cell on the lower row that is side-adjacent to his current cell. Since his current cell is on row i, any cell on row i+1 that is side-adjacent must share a side. The only side-adjacent cells are (i+1, j) (down), (i, j-1) (left), (i, j+1) (right). But left and right are on the same row, not lower row. So only down is on the lower row. So indeed only directly below.
But some might argue that "side-adjacent cell on the lower row" could mean a cell that is adjacent to the side of the current cell, and that cell is located on the lower row. That is exactly the cell directly below. So our interpretation is correct.
But is there any possibility that Om Nom could also jump to left-down or right-down? That would be a diagonal, which is not side-adjacent. The problem says "side-adjacent cell" to avoid diagonal. So it's clear.
Thus solution stands.
Now, we must consider that Om Nom could also possibly start at time 0 and then jump at time 0? No, he starts at time 0 at an upper row cell, then after one unit jumps to the next row. So timeline is as used.
We also need to ensure that the spiders' positions are considered at integer times, and they move simultaneously with Om Nom? The problem says: "In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. ... Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time." This suggests that at each integer time, both Om Nom and spiders update positions? Usually, they move in discrete steps: at time t (starting from 0), both are at some positions. Om Nom lands at his starting cell at time 0 (before moving). Then after 1 unit, he jumps to next cell, and simultaneously spiders move one step. So at time 1, he lands on the new cell and sees spiders after they moved. That matches our model: at time t, Om Nom is at row t+1 (if we index rows from 1). Spiders are at positions after t moves (since they started at time 0 at initial positions). So it's consistent.
Thus solution is straightforward.
Now let's examine constraints: n,m up to 2000, grid total cells up to 4 million. We can simply read the n lines as strings, loop over each character and update ans accordingly. That's O(n*m) time and O(m) memory, which is fine.
But careful: k can be up to m(n-1). That's okay.
We should verify that for U spider condition we didn't miss something about the row i being visited by Om Nom. Om Nom visits row i at time i-1. For U spider, at time t, it is at row r0 - t. We need t = i-1 and row i = r0 - t => i = r0 - (i-1) => i = (r0+1)/2. So i integer if r0 odd. Also we need that this row i is within the park and that Om Nom indeed visits it: he visits all rows from 1 to n. So if i <= n, it's visited. Since r0 <= n, i = (r0+1)/2 <= (n+1)/2 <= n for n>=1? For n=1? But n>=2 as per constraints (2 ≤ n). So fine. But what if n is 2 and r0=3? Not possible because r0 <= n. So it's fine.
But wait, could there be a scenario where r0 odd but (r0+1)/2 > n? If r0 = n+1? Not possible. So ok.
Now, we should also consider if any spider could be seen at time 0? Row1 has no spiders, but if a spider moves into row1 at time 0? Only if it started there, but that's not allowed. So no.
Thus solution is good.
But before finalizing, let's double-check the condition for L spider: col = c0 - (r0 - 1). But is there any other constraints about the spider not leaving earlier due to hitting left boundary before time r0-1? That's exactly c0 >= r0 ensures that at t = r0-1, column = c0 - (r0-1) >= 1. However, if c0 is large enough, the spider might still be inside. But if c0 < r0, then at time r0-1, column would be negative, so it would have left earlier. So condition is correct.
For R spider: condition ensures column at time r0-1 <= m.
One more subtlety: The spider might also leave because of row boundary? Only vertical spiders can leave via row. For L/R, they stay on same row, so no.
Now, check sample 4: we already matched.
So algorithm is just scanning and updating.
But wait, the problem statement says: "k spiders, each spider at time 0 is at some cell of the field." And input lines contain characters like 'L','R','U','D' for spiders, '.' for empty. So we read.
Edge cases: Could there be a spider with direction 'D'? It never contributes, but we don't need to process.
Complexities: O(n*m) = up to 4e6, which is fine.
Now, we need to produce output as m integers.
Implementation details: We'll read n,m,k (k may be ignored as it's just total spiders). Then loop i from 0 to n-1 (or 1..n). For each row string, for j from 0..m-1, get char ch. Based on ch:
if ch == 'L': if i+1 <= j+1: // 1-indexed row i+1, col j+1. Actually condition: row <= col. col_idx = (j+1) - (i) // since (r0-1) = i ans[col_idx-1] += 1 // because 0-indexed. elif ch == 'R': if (j+1) + (i+1) - 1 <= m: // c0 + r0 -1 <= m col_idx = (j+1) + i // (j+1)+(i+1)-1 = j+1 + i ans[col_idx-1] += 1 elif ch == 'U': if (i+1) % 2 == 1: // odd col_idx = j+1 ans[col_idx-1] += 1 else: // '.' or 'D' ignore.
But careful: For 'R' condition: col = c0 + r0 - 1. Since c0 = j+1, r0 = i+1, so col = j+1 + i+1 - 1 = j+1 + i = j + i + 1. So in 0-indexed terms: col_index = j + i + 1 (1-indexed). Check: i=1 (row2), j=0 (col1) => col=0+1+1=2, good. So in code: if j + i + 1 <= m then ans[j + i]++ (since 0-indexed answer array index = col-1). Similarly for L: col = c0 - (r0-1) = (j+1) - i = j+1 - i. So 1-indexed col = j+1 - i. Condition: i <= j? Actually r0 <= c0 => i+1 <= j+1 => i <= j. So condition: i <= j. In 0-indexed, row index i (0-based) <= column index j (0-based). Then col 1-indexed = j+1 - i. 0-indexed array index = (j - i). So ans[j - i]++.
For U: condition: row odd => (i+1) % 2 == 1 => i even? Because i+1 odd => i even. So if i%2==0? Let's check: row 1 (i=0) odd => i%2==0? 0%2==0, yes. row 2 (i=1) even => i%2==1. So condition: i%2==0. Then column index j. So ans[j]++.
So we can implement with 0-indexed loops.
Now, is there any scenario where L spider's computed column j - i could be out of bounds? Since we only process when i <= j, j - i is between 0 and m-1. So safe.
Similarly for R: j + i + 1 <= m, so index = j + i is between 0 and m-1.
For U: j between 0..m-1.
Thus code is simple.
But wait: The problem statement guarantees that first row has no spiders, but our loop includes row 0 (first row) - we can skip or just process, but there won't be spiders so it's fine.
Now, memory: ans array of size m (up to 2000). So fine.
Now, confirm with sample 4 using 0-indexed:
Row indices: i=1 (second row), j=0: char 'R', condition: j + i + 1 = 0+1+1=2 <=4 => index = j+i=1, ans[1]++ (col2). Good. i=1, j=1: 'R', 1+1+1=3<=4 => index=2, ans[2]++ (col3). i=1, j=2: 'L', condition i<=j? 1<=2 true => index=j-i=2-1=1? Actually j-i=1, ans[1]++ (col2). Wait but sample we had col2 from L spider: col=2 (c0-(r0-1)=3-(2-1)=2). Yes col2. i=1, j=3: 'L', i<=j (1<=3) true => index=j-i=3-1=2? Actually j-i=2, ans[2]++ (col3). That's correct. Row i=2 (third row), j=0: 'U', condition i%2==0? i=2 => 2%2==0 true => ans[0]++ (col1). j=1: 'U', ans[1]++ (col2) j=2: ans[2]++ (col3) j=3: ans[3]++ (col4) Matches.
Now, we must ensure that for U spiders, the condition i%2==0 is correct: i=2 (row3) is even index? row3 is odd row number, i=2 even. So indeed condition for row odd is i%2==0. So fine.
Now, we need to confirm that the spider's lifespan is indeed long enough for the meeting. For U spiders, we derived condition r0 odd. But also we must check that the spider hasn't left the park before that time due to row boundary? It leaves when row < 1. At time t = (r0-1)/2, row = r0 - (r0-1)/2 = (r0+1)/2, which is >=1. So fine. Also, need to check that the spider hasn't left earlier due to column boundary? Not relevant. So condition r0 odd suffices.
But wait, what about the scenario where r0 is odd but (r0+1)/2 > n? That can't happen because r0 <= n, so (r0+1)/2 <= (n+1)/2 <= n for n>=2? For n=2, (r0+1)/2 could be 1.5? Actually if r0=2 (even) we skip. If r0=1 (odd) but row1 no spiders. For n=3, r0=3 odd => (3+1)/2=2 <=3. For n=4, r0=3 odd =>2 <=4; r0=1? no. So always <= n. So no issue.
Now, what about D spiders? Could there be a D spider that could be seen if Om Nom's path is not straight down? But we are convinced it's straight down. However, let's double-check the problem description for possible alternative interpretation: "walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park)." That could be interpreted as he always goes to a cell in the next row, but maybe he can choose which adjacent cell on the lower row (down-left, down, down-right) to jump to? The phrase "side-adjacent cell on the lower row" is ambiguous: "side-adjacent cell" might refer to a cell that is side-adjacent, and that cell is on the lower row. As argued, only directly below shares a side. However, a cell on the lower row that is side-adjacent to the current cell would be the cell directly below, because that's the only cell on the lower row that shares a side. But what about the cell that is to the left or right? Those are on the same row, not lower. So indeed, only down.
But some problems define "side-adjacent" as four-directionally adjacent. Then a cell on the lower row that is side-adjacent to current cell could be down-left? Let's examine: current cell (i,j). The cells that are side-adjacent are (i-1,j), (i+1,j), (i,j-1), (i,j+1). Among these, which are on the lower row? (i+1,j) is on the lower row. (i,j-1) and (i,j+1) are on same row. So only one. So unambiguous.
Thus Om Nom's path is a simple vertical line down the column he started.
Thus solution stands.
But wait: Could Om Nom choose to jump outside before reaching the bottom? The phrase "or outside the park boundaries" suggests that from a cell, he could jump directly outside (maybe from any cell, he could jump out, ending the walk early). However, the problem says: "to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park)." This indicates his intention is to go down until he leaves; he might not choose to leave early. But even if he could, the optimal path (since he wants to avoid spiders? Actually he just wants to know how many he will see; there's no optimization in path, it's predetermined: he jumps down each time. The phrase "or outside the park boundaries" is just describing that a jump can go outside (when he is at the last row, jumping down leads outside). So it's fine.
Thus answer.
Now, we must confirm that the condition for L and R spiders is exactly that. But what about the possibility that the spider might be seen at a row different than r0? For horizontal spiders, row is constant. So only possible at row r0. For vertical spiders, column constant, so only possible at column c0. So yes.
But is there any other type of spider? Only four letters.
Thus solution is straightforward.
But we should also consider the possibility of spiders colliding and multiple spiders in the same cell at the same time. Our counting includes them individually (since we increment per spider). That's correct as per problem: he sees all spiders in that cell at that moment.
Now, we need to produce output as m integers.
Implementation plan:
- Read n, m, k (but k is redundant).
- Initialize ans = [0] * m.
- Loop i from 0 to n-1: read line s (length m). for j in range(m): ch = s[j] if ch == 'L': if i <= j: # row index i (0-based) <= column index j ans[j - i] += 1 elif ch == 'R': if j + i + 1 <= m: # because col = j+i+1 (1-indexed) <= m ans[j + i] += 1 elif ch == 'U': if i % 2 == 0: # row number (i+1) is odd ans[j] += 1 # else ignore '.' and 'D'
- Print ans as space-separated integers.
Check with sample 1: n=3,m=3. Row0: "..." skip. Row1 (i=1): "R.L". j=0: 'R': condition j+i+1=0+1+1=2 <=3 -> ans[1]++ (ans[1]=1). j=1: '.' skip. j=2: 'L': condition i<=j? 1<=2 true -> ans[2-1]=ans[1]++ -> ans[1]=2. Row2 (i=2): "R.U". j=0: 'R': condition 0+2+1=3 <=3 -> ans[2]++ (ans[2]=1). j=1: '.' skip. j=2: 'U': condition i%2==0? i=2 => true -> ans[2]++ => ans[2]=2. Thus ans = [0,2,2]? Wait ans indices: 0,1,2 -> ans[0]=0, ans[1]=2, ans[2]=2. Output: "0 2 2". Good.
Now test sample 2: n=2,m=2. Row0: ".." skip. Row1 (i=1): "RL". j=0: 'R': condition 0+1+1=2 <=2 -> ans[1]++ => ans[1]=1. j=1: 'L': condition i<=j? 1<=1 true -> ans[1-1]=ans[0]++ => ans[0]=1. Ans = [1,1] matches.
Sample3: Row1: "LR". j=0: 'L': i=1<=0? false -> no. j=1: 'R': 1+1+1=3>2 false. ans = [0,0].
Sample4: as computed matches.
Sample5: row1 (i=1): "UU". j=0: 'U': i%2==0? 1%2==0? false, so no. j=1: false. ans [0,0].
All good.
Now, we must consider that the input may have other characters? It's guaranteed only '.', 'L','R','U','D'. So okay.
Now, note the constraints: k can be 0; then answer all zeros.
Time complexity: O(n*m) = up to 4e6, which is fine in Python.
But we should be careful about I/O performance: reading 4 million characters may be fine. Use sys.stdin.read() or sys.stdin.readline.
Now, potential pitfalls: For L spiders, condition i <= j (0-index) is correct? For row index i, column index j. Need r0 <= c0 -> i+1 <= j+1 -> i <= j. Yes.
For R spiders, condition j + i + 1 <= m: col_1index = j+1 + i (since r0-1 = i) => j+1 + i <= m => j + i + 1 <= m. So condition j + i + 1 <= m.
Now, note that for R spiders, we should also consider if the spider might leave earlier because it goes out of bounds before time r0-1? Condition j + i + 1 <= m ensures that at time t = r0-1 = i, column = c0 + i = j+1 + i <= m, so still in bounds. Also need to ensure it hasn't left earlier? If it goes out exactly at time t = m - c0 + 1? Actually it leaves when column > m. The condition for being present at time i is that i <= m - c0. Since i = r0-1. So i <= m - (j+1) => i + j + 1 <= m. So same.
Now, for L spiders, condition i <= j ensures that at time i, column = j+1 - i >= 1.
All good.
Now, let's consider a more complicated scenario to double-check: Spider moving up, but what if row i = (r0+1)/2 is not integer? Then not seen. So we check r0 odd.
But wait: Could there be a scenario where the spider moves up and is seen at time t not equal to the exact meeting derived from equation? Because Om Nom visits row i at time i-1. The spider's row is r0 - t. To meet, we need i = r0 - t and t = i-1 => t = r0 - i and t = i-1 => r0 - i = i-1 => r0 = 2i-1 => i = (r0+1)/2. So indeed only if r0 odd. So correct.
Now, what about D spiders? Could there be a scenario where the spider moves down and Om Nom moves down and they meet if Om Nom starts at a later time? No, because both move synchronously.
Thus solution is complete.
However, before finalizing, let's consider the possibility of spiders that start on row 1? The problem guarantees row1 has no spiders. So no.
Now, confirm with the constraints: 2 ≤ n,m ≤ 2000, k ≤ m(n-1). The input size is about 4 million, reading line by line is okay.
Now, consider memory: ans array of size m (max 2000). So fine.
Now, we need to output m integers separated by spaces. Use ' '.join(map(str, ans)).
Now, one more test: Let's create a random small grid and simulate brute force to verify formulas. But we'll trust.
But before final answer, double-check the condition for U spider: row must be odd. But is it necessary that the meeting time t = (r0-1)/2 is integer and also t <= r0-1 (obviously). Also need that at that time, spider is still inside: row = (r0+1)/2 >= 1, which holds. However, could there be a situation where the spider moves up and then leaves the park before that time because it goes out from the side? No, only vertical.
Now, what about the possibility that the spider U might also be seen at time 0 if it started at row1? Not allowed.
Thus correct.
Now, we should also note that the problem statement: "The park can be represented as a rectangular n × m field." Row numbering: first row is upper row. So row1 is top. Spiders move: up means decreasing row number, down means increasing row number.
Now, Om Nom starts at an upper row cell of the field (first row). He jumps to a side-adjacent cell on the lower row. That seems to be exactly moving down.
Thus answer stands.
Now, I'd like to see if there is any hidden nuance: Could Om Nom choose to jump to a cell on the lower row that is not directly below, like if he jumps to a side-adjacent cell on the lower row? Let's parse: "side-adjacent cell on the lower row". Could "side-adjacent" modify "cell", and "on the lower row" is another condition? So the cell must be side-adjacent and also on the lower row. As argued, only one such cell. So yes.
But what if the park's rows are numbered top to bottom, and "lower row" means a row with higher index. The only side-adjacent cell on that row is the cell directly below. So fine.
Now, also note that the problem says "to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park)." That indicates his intention is to go down, not to wander left-right. So path is vertical.
Thus solution done.
Now, we should also think about large input and Python performance. Using a loop over characters in Python, performing simple if-else and integer addition, for up to 4e6 iterations, is fine. It might take ~0.2-0.3 seconds if optimized. We can perhaps use sys.stdin.buffer.read to read all and iterate. But using sys.stdin.readline per row is also okay.
Also, we need to output quickly.
Thus final solution:
Pseudo:
def main(): import sys data = sys.stdin.read().split() # First three ints: n,m,k # Then n strings it = iter(data) n = int(next(it)); m = int(next(it)); k = int(next(it)) ans = [0]*m for i in range(n): row = next(it) # row length m for j,ch in enumerate(row): if ch == 'L': if i <= j: ans[j-i] += 1 elif ch == 'R': if j+i+1 <= m: ans[j+i] += 1 elif ch == 'U': if i % 2 == 0: ans[j] += 1 # else ignore print(' '.join(map(str, ans)))
But careful: Using sys.stdin.read().split() will split on whitespace, and row strings contain no spaces, so it's fine. However, each row is a string with characters. That works.
Alternatively, use sys.stdin.readline per row to avoid storing all strings if memory is concern, but 4 million is fine.
Now, we might need to consider that k is not used; it's just for validation.
Now, let's test with sample 1 using this code mentally: works.
Now, consider potential off-by-one: In R spider condition, we used j+i+1 <= m. Suppose j+i+1 == m+1? Then out of bounds. So condition ensures col index 1-indexed <= m. In 0-indexed, col index = j+i, which is <= m-1 when j+i+1 <= m => j+i <= m-1. So safe.
For L spider, condition i <= j ensures j-i >=0, and col index = j-i. The column 1-indexed = j-i+1. This is automatically <= m because j <= m-1, and i>=0, so j-i+1 <= m. However, we also need to ensure that column >=1, which is ensured by j>=i. So condition is sufficient.
Now, what about L spider where j-i+1 > m? That would require j-i+1 > m => j > m-1 + i? But j max is m-1, so j-i+1 <= m - i + i? Actually max j = m-1, min i = 0 => max j-i+1 = m, so okay. So no need additional.
Now, U spider: condition i%2==0 ensures row odd. Could there be a case where row odd but the meeting row i ( (r0+1)/2 ) is > n? As argued, r0 <= n, so (r0+1)/2 <= (n+1)/2 <= n? For n=2, (2+1)/2=1.5 not integer, so condition fails because r0 even. For n=3, r0=3 -> (3+1)/2=2 <=3, ok. For n=4, r0=3 ->2 <=4, ok; r0=5 not possible. So fine.
Thus solution stands.
But wait, what about the possibility that a spider could be seen multiple times if it is both moving horizontally and vertically? No, each spider moves in a fixed single direction.
Thus solution is correct.
Now, we could also think about a direct combinatorial method, but already simple.
Now, one more test: Suppose a spider L at (2,2). i=1, j=1. i<=j true => col idx = j-i=0 (col1). So ans[0]++. Let's brute: r0=2,c0=2. At time t=1, col=2-1=1, row=2. Om Nom at col1 row2 at t=1? Wait if he starts at col1, then row2 col1 at t=1. But our computed col=1 corresponds to starting column 1. So yes, he would see it if he starts at column1. Check: Starting at col1, path: (1,1) t0, (2,1) t1. Spider at t1: (2,1) yes. So correct.
Now, consider spider R at (2,2). i=1,j=1. j+i+1=1+1+1=3 <= m? If m=3, yes. col idx = j+i=2 (col3). Starting at col3, path: (2,3) at t1. Spider at t1: (2,3)? Actually spider R at (2,2) moves right: t1: (2,3). Yes. So correct.
Now, consider U spider at (3,2). i=2, j=1. i%2==0 true => ans[1]++ (col2). Starting col2: path: (1,2) t0, (2,2) t1, (3,2) t2. Spider at t? t = (r0-1)/2 = (3-1)/2=1. So at t=1, spider at (2,2). Om Nom at (2,2) t1. So sees. So correct.
Now, consider U spider at (4,2). i=3, j=1. i%2==0? 3%2=1, false. So no. Check: r0=4 even. t would be (4-1)/2=1.5 not integer. Could there be a meeting at some other time? No because equation needed.
Thus correct.
Now, check D spider at (2,2): no condition. That seems right.
Now, we must consider if there is any scenario where a spider could be seen at time 0? Starting row1, but row1 no spiders, so no.
Thus answer is correct.
Now, confirm with another custom scenario: n=5,m=5. L spider at (5,5). i=4, j=4. Condition i<=j true (4<=4) => col idx = 4-4=0 => col1. So starting col1, would he see? Starting col1: path: row5 at t4. Spider L: at time t = r0-1 =4, column = 5 - 4 =1. So yes, at t=4, (5,1). So sees. Good.
Now, R spider at (5,1): i=4,j=0. Condition j+i+1=0+4+1=5 <=5 true => col idx=4 => col5. Starting col5: path row5 col5 at t4? Actually row5 col5 at t4. Spider at t4: column = 1+4=5, row=5. Yes.
Now, U spider at (5,2): i=4,j=1. i%2==0 true => col idx=1 => col2. Starting col2: row? Meeting at time t=(5-1)/2=2, row = (5+1)/2=3. But spider at t2: row=5-2=3, col=2. Om Nom at t2: row3 col2. So yes.
Now, U spider at (5,2) with n=5. Good.
Now, I'm satisfied.
Thus answer.
Now, we need to produce final solution explanation.
But before writing final answer, let's read the problem statement again to ensure there's no nuance about Om Nom's jump: "One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries." The phrase "either a side-adjacent cell on the lower row or outside" might be interpreted as: from his current cell, there are multiple options: he could jump to any side-adjacent cell that is on the lower row, or he could jump outside. That would imply that from a cell, there might be multiple side-adjacent cells on the lower row? As argued, only directly below. But what about if we consider the cell to the lower-left? That's not side-adjacent. So indeed only one.
But maybe they consider the lower row as row i+1, and side-adjacent cells of the current cell that are on that row could be the cell directly below (since it shares a side) and maybe also the cell diagonally? No, diagonals don't share a side. So it's unique.
Thus fine.
Now, we should also consider the possibility that Om Nom could start at a cell on the first row and then at each step, he chooses which direction to jump (maybe left-down or right-down) but only to side-adjacent cells on the lower row. However, if he could choose, then the path might not be fixed, and the problem would ask for the optimal starting cell with minimal spiders? But the problem asks: "for each possible starting cell, how many spiders will he see during the walk if he starts from this cell?" It doesn't say he can choose jumps; it says he walks by moving down the field. The description of the jump is just to describe the movement mechanics; it doesn't say he can choose between multiple options. However, the phrase "either ... or ..." might be describing the two possible outcomes of a jump: either he lands on a cell on the lower row (if one exists) or he leaves the park (if he's at the bottom). So it's not a choice; it's a deterministic outcome: he always tries to go to the lower row, and if there is a side-adjacent cell on the lower row (which there is, as long as he's not at the bottom? Actually at row n, there is no lower row, so the only way to move is to go outside. So at each step, if there is a lower row, he jumps to the side-adjacent cell on that row. But which one? It must be directly below because it's side-adjacent. So the path is deterministic: from (i,j) he goes to (i+1, j) if i < n, else he leaves. So indeed no choices.
Thus the walk is predetermined.
Thus solution stands.
Now, confirm that for row n, he jumps outside, so he doesn't land on any cell at time n. So we only consider rows 1..n at times 0..n-1.
Now, we must check if there is any scenario where he might land on a cell outside the grid? No, he only lands on cells within the grid.
Now, one more nuance: The problem says: "to start walking at time 0 at an upper row cell of the field (it is guaranteed that the cells in this row do not contain any spiders);" That means he starts at time 0 on a cell of the first row. He may start at any column. Then "to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park)." So he intends to go down, so his jumps are downward. So yes.
Now, we must ensure that for L and R spiders, we didn't miss that the spider might be seen also at time 0? No.
Now, what about spiders that move up and could be seen at row 1? That would be at time t = r0 - 1 (since row becomes 1). But Om Nom visits row 1 at time 0 only. For a spider to be at row 1 at time 0, it would have to start at row1, which is prohibited. Could a spider moving up be at row 1 at time t = r0 - 1? That's when row becomes 1. Om Nom visits row 1 at time 0 only, not at later times. So unless r0 - 1 = 0 => r0 = 1, not allowed. So no.
Thus no extra.
Now, we should also think about potential integer overflow? No, k up to 4e6, so answer fits in 32-bit int.
Thus solution is complete.
Now, we will produce final answer.
But before final, consider the possibility of D spiders being seen if Om Nom could also move up? No.
Now, let's think about the sample 1 again: they had a note about a cell containing two spiders at same time (represented by "*"). That's exactly the (2,2) at time1. So our counting includes both.
Thus final.
Now, I'll produce a solution with explanation.
Implementation notes: Use fast I/O.
Potential micro-optimizations: Because n and m up to 2000, double loop is fine.
Now, we should also note that we ignore 'D' spiders; they never contribute.
Now, possible alternative approach: Precompute contributions using difference arrays? But not needed.
Now, final answer.
But wait, what about memory usage of reading all lines? It's fine.
Now, write final solution.
Let's produce final answer in code. ```python import sys
def main(): data = sys.stdin.read().split() it = iter(data) n = int(next(it)) m = int(next(it)) k = int(next(it)) # not used ans = [0] * m
for i in range(n): # i = 0..n-1, corresponds to row i+1 row = next(it) # row length is m for j, ch in enumerate(row): if ch == 'L': if i <= j: # condition r <= c ans[j - i] += 1 elif ch == 'R': if j + i + 1 <= m: # condition c + r - 1 <= m ans[j + i] += 1 elif ch == 'U': if i % 2 == 0: # row i+1 is odd ans[j] += 1 # 'D' and '.' are ignored print(' '.join(map(str, ans)))if name == 'main': main()