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.

<image>

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. 
3 7 14
.......
LDUDLLD
DLRDDLD
 4 5 15
.....
DRRLR
ULDLD
DLRRL
 10 8 30
........
.L.LDRR.
D.LDLR.U
..RL.L..
UR.UL...
.D.....L
R..UDULL
........
DD.U...D
........
 5 6 20
......
.UURD.
LUD.RR
U.LDDD
DDLDDU
 5 7 19
.......
RDLLLRL
UUR..U.
.D.DLLL
..R..UU
 8 9 28
.........
.R.LDR.D.
....UULU.
R.D..DL.L
.R..DLUDU
R........
.URU...UU
.....D.L.
 10 10 47
..........
.R.LLL.R.L
R.ULUL.RUL
RD..RL.L..
RU.D....LU
..RRR..DL.
.DRUUD.ULD
...D...LDD
...UUU.U..
R.....D...
 2 2 0
..
..
 100 2 45
..
.D
U.
..
U.
..
..
..
U.
..
..
D.
U.
..
..
.D
DU
..
UD
..
..
..
..
..
..
D.
U.
..
..
D.
U.
..
..
..
U.
..
..
.D
..
..
.D
..
..
.D
.U
D.
..
.D
..
..
UD
..
U.
..
U.
..
UD
..
U.
..
U.
..
..
..
U.
..
..
D.
..
..
U.
..
U.
..
UU
..
U.
..
U.
..
..
..
..
..
..
..
..
..
.D
..
..
D.
U.
.D
..
..
U.
.D
U.
..
 2 100 59
....................................................................................................
.DR.D..DLLR.LDRR..L.LDRRRDLD.LDRR.LLR.R...DRLD.RRLL.L.D..R.LD.DL....LR.LR.DRLD.....L.D..RD...D.LL.R.
 5 5 10
.....
RU.D.
..DLL
.D...
RL..L

0 0 0 2 2 0 0  1 2 2 1 0  6 1 4 3 0 3 2 3  0 1 0 0 1 1  1 4 2 2 1 3 3  1 2 2 3 2 4 2 2 3  1 2 6 6 7 1 0 5 5 4  0 0  23 3  0 0 0 1 0 0 0 1 1 0 0 2 0 0 0 1 1 1 0 1 0 0 0 1 1 2 0 0 1 0 0 0 1 2 1 0 0 1 0 1 0 0 0 1 1 0 0 0 2 2 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 1 0 0 2 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1  1 2 1 0 1 
    import java.io.*;
    import java.math.BigDecimal;
    import java.math.RoundingMode;
    import java.util.*;

    import javax.lang.model.type.IntersectionType;
    import javax.swing.text.html.CSS;
    public class codeforces {
        static class FastReader {
            BufferedReader br;
            StringTokenizer st;

            public FastReader() {
                br = new BufferedReader(new InputStreamReader(System.in));
            }

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

            int nextInt() {
                return Integer.parseInt(next());
            }

            long nextLong() {
                return Long.parseLong(next());
            }

            double nextDouble() {
                return Double.parseDouble(next());
            }

            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }
        }
        static class Pair{
            int a,b;
            Pair(int a,int b){
                this.a=a;
                this.b=b;
            }
        }
       public static void main(String[] args) throws IOException {
           PrintWriter out = new PrintWriter(System.out);
           InputReader sc = new InputReader(System.in);
           int n=sc.nextInt();
           int m=sc.nextInt();
           int k=sc.nextInt();
           char[][] a=new char[n][m];
           for(int i=0;i<n;i++) {
               String s = sc.next();
               for (int j = 0; j < m; j++)
                   a[i][j] = s.charAt(j);
           }
           int[][] arr=new int[n][m];
           for(int i=0;i<m;i++) {
               int c = 0;
               for (int j = 1; j < n; j++) {
                   if (i != 0 && i - j >= 0) {
                       if (a[j][i - j] == 'R')
                           c++;
                   }
                   if (i != m - 1 && m - i - j > 0) {
                       if (a[j][i + j] == 'L')
                           c++;
                   }
                   if (j != n - 1 && 2 * j < n) {
                       if (a[2 * j][i] == 'U')
                           c++;
                   }
               }
               System.out.print(c + " ");
           }

        }


           static class InputReader {
            private InputStream in;
            private byte[] buffer = new byte[1024];
            private int curbuf;
            private int lenbuf;
            public InputReader(InputStream in) {
                this.in = in;
                this.curbuf = this.lenbuf = 0;
            }
            public boolean hasNextByte() {
                if (curbuf >= lenbuf) {
                    curbuf = 0;
                    try {
                        lenbuf = in.read(buffer);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (lenbuf <= 0)
                        return false;
                }
                return true;
            }

            private int readByte() {
                if (hasNextByte())
                    return buffer[curbuf++];
                else
                    return -1;
            }

            private boolean isSpaceChar(int c) {
                return !(c >= 33 && c <= 126);
            }

            private void skip() {
                while (hasNextByte() && isSpaceChar(buffer[curbuf]))
                    curbuf++;
            }

            public boolean hasNext() {
                skip();
                return hasNextByte();
            }

            public String next() {
                if (!hasNext())
                    throw new NoSuchElementException();
                StringBuilder sb = new StringBuilder();
                int b = readByte();
                while (!isSpaceChar(b)) {
                    sb.appendCodePoint(b);
                    b = readByte();
                }
                return sb.toString();
            }

            public int nextInt() {
                if (!hasNext())
                    throw new NoSuchElementException();
                int c = readByte();
                while (isSpaceChar(c))
                    c = readByte();
                boolean minus = false;
                if (c == '-') {
                    minus = true;
                    c = readByte();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res = res * 10 + c - '0';
                    c = readByte();
                } while (!isSpaceChar(c));
                return (minus) ? -res : res;
            }

            public long nextLong() {
                if (!hasNext())
                    throw new NoSuchElementException();
                int c = readByte();
                while (isSpaceChar(c))
                    c = readByte();
                boolean minus = false;
                if (c == '-') {
                    minus = true;
                    c = readByte();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res = res * 10 + c - '0';
                    c = readByte();
                } while (!isSpaceChar(c));
                return (minus) ? -res : res;
            }

            public double nextDouble() {
                return Double.parseDouble(next());
            }

            public int[] nextIntArray(int n) {
                int[] a = new int[n];
                for (int i = 0; i < n; i++)
                    a[i] = nextInt();
                return a;
            }

            public long[] nextLongArray(int n) {
                long[] a = new long[n];
                for (int i = 0; i < n; i++)
                    a[i] = nextLong();
                return a;
            }

            public char[][] nextCharMap(int n, int m) {
                char[][] map = new char[n][m];
                for (int i = 0; i < n; i++)
                    map[i] = next().toCharArray();
                return map;
            }
        }
    }
    class SegTree<S> {
        final int MAX;

        final int N;
        final java.util.function.BinaryOperator<S> op;
        final S E;

        final S[] data;

        @SuppressWarnings("unchecked")
        public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) {
            this.MAX = n;
            int k = 1;
            while (k < n) k <<= 1;
            this.N = k;
            this.E = e;
            this.op = op;
            this.data = (S[]) new Object[N << 1];
            java.util.Arrays.fill(data, E);
        }

        public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) {
            this(dat.length, op, e);
            build(dat);
        }

        private void build(S[] dat) {
            int l = dat.length;
            System.arraycopy(dat, 0, data, N, l);
            for (int i = N - 1; i > 0; i--) {
                data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);
            }
        }

        public void set(int p, S x) {
            exclusiveRangeCheck(p);
            data[p += N] = x;
            p >>= 1;
            while (p > 0) {
                data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);
                p >>= 1;
            }
        }

        public S get(int p) {
            exclusiveRangeCheck(p);
            return data[p + N];
        }

        public S prod(int l, int r) {
            if (l > r) {
                throw new IllegalArgumentException(
                        String.format("Invalid range: [%d, %d)", l, r)
                );
            }
            inclusiveRangeCheck(l);
            inclusiveRangeCheck(r);
            S sumLeft = E;
            S sumRight = E;
            l += N; r += N;
            while (l < r) {
                if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]);
                if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight);
                l >>= 1; r >>= 1;
            }
            return op.apply(sumLeft, sumRight);
        }

        public S allProd() {
            return data[1];
        }

        public int maxRight(int l, java.util.function.Predicate<S> f) {
            inclusiveRangeCheck(l);
            if (!f.test(E)) {
                throw new IllegalArgumentException("Identity element must satisfy the condition.");
            }
            if (l == MAX) return MAX;
            l += N;
            S sum = E;
            do {
                l >>= Integer.numberOfTrailingZeros(l);
                if (!f.test(op.apply(sum, data[l]))) {
                    while (l < N) {
                        l = l << 1;
                        if (f.test(op.apply(sum, data[l]))) {
                            sum = op.apply(sum, data[l]);
                            l++;
                        }
                    }
                    return l - N;
                }
                sum = op.apply(sum, data[l]);
                l++;
            } while ((l & -l) != l);
            return MAX;
        }

        public int minLeft(int r, java.util.function.Predicate<S> f) {
            inclusiveRangeCheck(r);
            if (!f.test(E)) {
                throw new IllegalArgumentException("Identity element must satisfy the condition.");
            }
            if (r == 0) return 0;
            r += N;
            S sum = E;
            do {
                r--;
                while (r > 1 && (r & 1) == 1) r >>= 1;
                if (!f.test(op.apply(data[r], sum))) {
                    while (r < N) {
                        r = r << 1 | 1;
                        if (f.test(op.apply(data[r], sum))) {
                            sum = op.apply(data[r], sum);
                            r--;
                        }
                    }
                    return r + 1 - N;
                }
                sum = op.apply(data[r], sum);
            } while ((r & -r) != r);
            return 0;
        }

        private void exclusiveRangeCheck(int p) {
            if (p < 0 || p >= MAX) {
                throw new IndexOutOfBoundsException(
                        String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX)
                );
            }
        }

        private void inclusiveRangeCheck(int p) {
            if (p < 0 || p > MAX) {
                throw new IndexOutOfBoundsException(
                        String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX)
                );
            }
        }
    }
    class MathLib{
        static long fastPow(long a, long b, long mod) {
            if(b == 0)
                return 1L;

            long val = fastPow(a, b/2, mod);
            if(b % 2 == 0)
                return val * val % mod;
            else
                return val * val % mod * a % mod;
        }
        static int LowerBound(int a[], int x) { // x is the target value or key
            int l=-1,r=a.length;
            while(l+1<r) {
                int m=(l+r)>>>1;
                if(a[m]>=x) r=m;
                else l=m;
            }
            return r;
        }
        static int UpperBound(int a[], int x) {// x is the key or target value
            int l=-1,r=a.length;
            while(l+1<r) {
                int m=(l+r)>>>1;
                if(a[m]<=x) l=m;
                else r=m;
            }
            return l+1;
        }
        private static long safe_mod(long x, long m){
            x %= m;
            if(x<0) x += m;
            return x;
        }

        private static long[] inv_gcd(long a, long b){
            a = safe_mod(a, b);
            if(a==0) return new long[]{b,0};

            long s=b, t=a;
            long m0=0, m1=1;
            while(t>0){
                long u = s/t;
                s -= t*u;
                m0 -= m1*u;
                long tmp = s; s = t; t = tmp;
                tmp = m0; m0 = m1; m1 = tmp;
            }
            if(m0<0) m0 += b/s;
            return new long[]{s,m0};
        }

        public static long gcd(long a, long b){
            a = java.lang.Math.abs(a);
            b = java.lang.Math.abs(b);
            return inv_gcd(a, b)[0];
        }
        public static long lcm(long a, long b){
            a = java.lang.Math.abs(a);
            b = java.lang.Math.abs(b);
            return a / gcd(a,b) * b;
        }

        public static long pow_mod(long x, long n, int m){
            assert n >= 0;
            assert m >= 1;
            if(m == 1)return 0L;
            x = safe_mod(x, m);
            long ans = 1L;
            while(n > 0){
                if((n&1) == 1) ans = (ans * x) % m;
                x = (x*x) % m;
                n >>>= 1;
            }
            return ans;
        }

        public static long[] crt(long[] r, long[] m){
            assert(r.length == m.length);
            int n = r.length;

            long r0=0, m0=1;
            for(int i=0; i<n; i++){
                assert(1 <= m[i]);
                long r1 = safe_mod(r[i], m[i]), m1 = m[i];
                if(m0 < m1){
                    long tmp = r0; r0 = r1; r1 = tmp;
                    tmp = m0; m0 = m1; m1 = tmp;
                }
                if(m0%m1 == 0){
                    if(r0%m1 != r1) return new long[]{0,0};
                    continue;
                }

                long[] ig = inv_gcd(m0, m1);
                long g = ig[0], im = ig[1];

                long u1 = m1/g;
                if((r1-r0)%g != 0) return new long[]{0,0};

                long x = (r1-r0) / g % u1 * im % u1;

                r0 += x * m0;
                m0 *= u1;
                if(r0<0) r0 += m0;
                //System.err.printf("%d %d\n", r0, m0);
            }
            return new long[]{r0, m0};
        }
        public static long floor_sum(long n, long m, long a, long b){
            long ans = 0;
            if(a >= m){
                ans += (n-1) * n * (a/m) / 2;
                a %= m;
            }
            if(b >= m){
                ans += n * (b/m);
                b %= m;
            }

            long y_max = (a*n+b) / m;
            long x_max = y_max * m - b;
            if(y_max == 0) return ans;
            ans += (n - (x_max+a-1)/a) * y_max;
            ans += floor_sum(y_max, a, m, (a-x_max%a)%a);
            return ans;
        }

        public static java.util.ArrayList<Long> divisors(long n){
            java.util.ArrayList<Long> divisors = new ArrayList<>();
            java.util.ArrayList<Long> large = new ArrayList<>();

            for(long i=1; i*i<=n; i++) if(n%i==0){
                divisors.add(i);
                if(i*i<n) large.add(n/i);
            }
            for(int p=large.size()-1; p>=0; p--){
                divisors.add(large.get(p));
            }
            return divisors;
        }
    }
