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 
#include <bits/stdc++.h>
using namespace std;
void RD(int &x) { scanf("%d", &x); }
void RD(unsigned int &x) { scanf("%u", &x); }
void RD(double &x) { scanf("%lf", &x); }
void RD(int &x, int &y) { scanf("%d%d", &x, &y); }
void RD(unsigned int &x, unsigned int &y) { scanf("%u%u", &x, &y); }
void RD(double &x, double &y) { scanf("%lf%lf", &x, &y); }
void RD(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void RD(unsigned int &x, unsigned int &y, unsigned int &z) {
  scanf("%u%u%u", &x, &y, &z);
}
void RD(double &x, double &y, double &z) { scanf("%lf%lf%lf", &x, &y, &z); }
void RD(char &x) { x = getchar(); }
void RD(char *s) { scanf("%s", s); }
void RD(string &s) { cin >> s; }
void PR(int x) { printf("%d\n", x); }
void PR(int x, int y) { printf("%d %d\n", x, y); }
void PR(unsigned int x) { printf("%u\n", x); }
void PR(unsigned long long x) { cout << x << endl; }
void PR(double x) { printf("%.4lf\n", x); }
void PR(char x) { printf("%c\n", x); }
void PR(char *x) { printf("%s\n", x); }
void PR(string x) { cout << x << endl; }
void upMin(int &x, int y) {
  if (x > y) x = y;
}
void upMin(long long &x, long long y) {
  if (x > y) x = y;
}
void upMin(double &x, double y) {
  if (x > y) x = y;
}
void upMax(int &x, int y) {
  if (x < y) x = y;
}
void upMax(long long &x, long long y) {
  if (x < y) x = y;
}
void upMax(double &x, double y) {
  if (x < y) x = y;
}
int sgn(double x) {
  if (x > 1e-10) return 1;
  if (x < -1e-10) return -1;
  return 0;
}
long long Gcd(long long x, long long y) {
  if (x < 0) x = -x;
  if (y < 0) y = -y;
  if (y == 0) return x;
  return Gcd(y, x % y);
}
long long Lcm(long long x, long long y) { return x / Gcd(x, y) * y; }
long long eular(long long n) {
  long long ans = n, i;
  for (i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans -= ans / i;
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans -= ans / n;
  return ans;
}
long long exGcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long temp = exGcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - a / b * y;
  return temp;
}
long long gcdReverse(long long a, long long b) {
  long long x, y;
  exGcd(a, b, x, y);
  x %= b;
  if (x < 0) x += b;
  return x;
}
long long myPow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}
long long myPow(long long a, long long b, long long mod) {
  a %= mod;
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
long long getInt() {
  long long x = 0, flag = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    flag = -1, c = getchar();
    while (!isdigit(c)) c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * flag;
}
long long getSqrt(long long t) {
  long long p = sqrt(1.0 * t);
  while (p * p > t) p--;
  while ((p + 1) <= t / (p + 1)) p++;
  return p;
}
struct point {
  double x, y;
  point() {}
  point(double _x, double _y) {
    x = _x;
    y = _y;
  }
  void get() { scanf("%lf%lf", &x, &y); }
  point operator+(point a) { return point(x + a.x, y + a.y); }
  point operator-(point a) { return point(x - a.x, y - a.y); }
  point operator*(double t) { return point(x * t, y * t); }
  double operator*(point a) { return x * a.y - y * a.x; }
  double operator^(point a) { return x * a.x + y * a.y; }
  double Len() { return sqrt(x * x + y * y); }
  point adjustTo(double L) {
    L /= Len();
    return point(x * L, y * L);
  }
  point operator/(double t) { return point(x / t, y / t); }
  double rotateAngle(point a) {
    point p = *this;
    return atan2(p * a, p ^ a);
  }
  int operator==(point a) { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0; }
  void print() { printf("%.4lf %.4lf\n", x, y); }
};
double calPloyArea(point a[], int n) {
  double ans = 0;
  int i;
  for (i = 0; i < n; i++) ans += a[i] * a[(i + 1) % n];
  return ans;
}
int changeToClockwise(point a[], int n) {
  double s = calPloyArea(a, n);
  if (sgn(s) >= 0) return 0;
  int L = 0, R = n - 1;
  while (L < R) swap(a[L++], a[R--]);
  return 1;
}
int pointOnSeg(point p, point a, point b) {
  if (sgn((p - a) * (p - b))) return 0;
  int x = sgn((p.x - a.x) * (p.x - b.x));
  int y = sgn((p.y - a.y) * (p.y - b.y));
  return x <= 0 && y <= 0;
}
int pointOnRightOfLine(point p, point a, point b) {
  return sgn((p - a) * (b - a)) > 0;
}
int pointOnLine(point p, point a, point b) {
  return sgn((p - a) * (b - a)) == 0;
}
int pointOnLeftOfLine(point p, point a, point b) {
  return sgn((b - a) * (p - a)) > 0;
}
int getRelationOfPointAndPloy(point a[], int n, point p) {
  a[n] = a[0];
  int i;
  double sum = 0;
  for (i = 0; i < n; i++) {
    if (pointOnSeg(p, a[i], a[i + 1])) return 0;
    point aa = a[i] - p;
    point bb = a[i + 1] - p;
    sum += aa.rotateAngle(bb);
  }
  if (fabs(sum - 2 * acos(-1.0)) < 1e-2) return -1;
  return 1;
}
int isParal(point a, point b, point p, point q) {
  double aa = (b.x - a.x) * (p.y - q.y);
  double bb = (b.y - a.y) * (p.x - q.x);
  return sgn(aa - bb) == 0;
}
int lineCrossLine(point a, point b, point p, point q, point &ans) {
  if (isParal(a, b, p, q)) {
    if (!pointOnLine(p, a, b)) return 0;
    return 2;
  }
  double s1 = (p - a) * (q - a);
  double s2 = (q - b) * (p - b);
  ans = (a * s2 + b * s1) / (s1 + s2);
  return 1;
}
int segCrossSeg(point a, point b, point p, point q, point &ans) {
  if (isParal(a, b, p, q)) {
    if (!pointOnLine(p, a, b)) return 0;
    if (sgn(a.x - b.x) == 0) {
      if (p.y > q.y) swap(p, q);
      if (a.y > b.y) swap(a, b);
      if (sgn(q.y - a.y) == -1 || sgn(b.y - p.y) == -1) return 0;
      if (q == a || p == b) {
        if (q == a) ans = q;
        if (p == b) ans = p;
        return 1;
      }
      return 2;
    }
    if (p.x > q.x) swap(p, q);
    if (a.x > b.x) swap(a, b);
    if (sgn(q.x - a.x) == -1 || sgn(b.x - p.x) == -1) return 0;
    if (q == a || p == b) {
      if (q == a) ans = q;
      if (p == b) ans = p;
      return 1;
    }
    return 2;
  }
  lineCrossLine(a, b, p, q, ans);
  if (pointOnSeg(ans, a, b) && pointOnSeg(ans, p, q)) return 1;
  return 0;
}
const long long MM = 1000000000000LL;
struct BigInteger {
  long long a[20];
  int cnt;
  BigInteger() {
    cnt = 1;
    a[1] = 0;
  }
  BigInteger(long long x) {
    if (x == 0) {
      cnt = 1;
      a[1] = 0;
      return;
    }
    cnt = 1;
    a[1] = x;
  }
  void reset() {
    cnt = 1;
    a[1] = 0;
  }
  BigInteger operator*(int x) {
    if (x == 0) return BigInteger(0);
    if (zero()) return BigInteger(0);
    BigInteger p = *this;
    int i;
    for (i = 1; i <= p.cnt; i++) p.a[i] *= x;
    int t = 0;
    for (i = 1; i <= p.cnt; i++) {
      p.a[i] += t;
      t = p.a[i] / MM;
      p.a[i] %= MM;
    }
    if (t == 0) return p;
    while (t) p.a[++p.cnt] = t % MM, t /= MM;
    return p;
  }
  int zero() { return cnt == 1 && a[1] == 0; }
  BigInteger operator+(BigInteger a) {
    if (a.zero()) return *this;
    if (zero()) return a;
    BigInteger p, q;
    if (a.cnt > cnt)
      p = a, q = *this;
    else
      p = *this, q = a;
    int i;
    for (i = 1; i <= q.cnt; i++) p.a[i] += q.a[i];
    int re = 0;
    for (i = 1; i <= p.cnt; i++) {
      p.a[i] += re;
      re = p.a[i] / MM;
      p.a[i] %= MM;
    }
    if (re) {
      p.a[++p.cnt] = re;
    }
    return p;
  }
};
const long long inf = (((long long)1) << 61) + 5;
const double dinf = 1000000000;
const int INF = 1000000005;
const int N = 222225;
struct SegTree {
  struct node {
    int L, R, size;
    double v;
  };
  node a[N << 2];
  int n;
  SegTree() {}
  SegTree(int x) {
    n = x;
    build(1, 1, n);
  }
  void build(int t, int L, int R) {
    a[t].L = L;
    a[t].R = R;
    if (L == R) {
      a[t].size = 0;
      a[t].v = 0;
      return;
    }
    int M = (L + R) >> 1;
    build(t << 1, L, M);
    build(t << 1 | 1, M + 1, R);
    a[t].size = a[t << 1].size + a[t << 1 | 1].size;
  }
  int query(int t, double v) {
    if (a[t].L == a[t].R) return a[t].v > v;
    if (sgn(a[t << 1].v - v) <= 0) return query(t << 1 | 1, v);
    return a[t << 1 | 1].size + query(t << 1, v);
  }
  void change(int t, int pos, double v) {
    if (a[t].L == a[t].R) {
      a[t].size = 1;
      a[t].v = v;
      return;
    }
    int M = (a[t].L + a[t].R) >> 1;
    if (pos <= M)
      change(t << 1, pos, v);
    else
      change(t << 1 | 1, pos, v);
    a[t].v =
        ((a[t << 1].v) > (a[t << 1 | 1].v) ? (a[t << 1].v) : (a[t << 1 | 1].v));
    a[t << 1 | 1].size = query(t << 1 | 1, a[t << 1].v);
    a[t].size = a[t << 1].size + a[t << 1 | 1].size;
  }
};
struct heapTree {
  struct heapNode {
    int L, R, pri, size;
    long long x, y;
    heapNode() {}
    heapNode(long long _x, long long _y) {
      x = _x;
      y = _y;
      if (x < 0) x = -x, y = -y;
      long long tmp = Gcd(x, y);
      x /= tmp;
      y /= tmp;
    }
    int operator>=(const heapNode &a) const { return *this == a || *this > a; }
    int operator<=(const heapNode &a) const { return *this < a || *this == a; }
    int operator==(const heapNode &a) const { return y * a.x == x * a.y; }
    int operator<(const heapNode &a) const { return y * a.x < x * a.y; }
    int operator>(const heapNode &a) const { return y * a.x > x * a.y; }
  };
  heapNode a[200005];
  int e, root;
  void init() {
    e = 0;
    root = -1;
  }
  void pushUp(int x) {
    if (x == -1) return;
    a[x].size = 1;
    if (a[x].L != -1) a[x].size += a[a[x].L].size;
    if (a[x].R != -1) a[x].size += a[a[x].R].size;
  }
  void rotL(int &x) {
    int y = a[x].R;
    a[x].R = a[y].L;
    pushUp(x);
    a[y].L = x;
    pushUp(y);
    x = y;
  }
  void rotR(int &x) {
    int y = a[x].L;
    a[x].L = a[y].R;
    pushUp(x);
    a[y].R = x;
    pushUp(y);
    x = y;
  }
  void insert(int &k, heapNode p) {
    if (k == -1) {
      k = ++e;
      a[k].L = a[k].R = -1;
      a[k].x = p.x;
      a[k].y = p.y;
      a[k].pri = rand();
    } else if (p < a[k]) {
      insert(a[k].L, p);
      if (a[a[k].L].pri > a[k].pri) rotR(k);
    } else {
      insert(a[k].R, p);
      if (a[a[k].R].pri > a[k].pri) rotL(k);
    }
    pushUp(k);
  }
  void insert(long long x, long long y) { insert(root, heapNode(x, y)); }
  void del(int &k, heapNode p) {
    if (k == -1)
      return;
    else if (p < a[k])
      del(a[k].L, p);
    else if (p > a[k])
      del(a[k].R, p);
    else {
      if (a[k].L == -1 && a[k].R == -1)
        k = -1;
      else if (a[k].L == -1)
        k = a[k].R;
      else if (a[k].R == -1)
        k = a[k].L;
      else {
        if (a[a[k].L].pri < a[a[k].R].pri) {
          rotL(k);
          del(a[k].L, p);
        } else {
          rotR(k);
          del(a[k].R, p);
        }
      }
    }
    pushUp(k);
  }
  void del(long long x, long long y) { del(root, heapNode(x, y)); }
  int findSmallThan(int k, heapNode p) {
    if (k == -1) return 0;
    if (p <= a[k]) return findSmallThan(a[k].L, p);
    int ans = 1;
    if (a[k].L != -1) ans += a[a[k].L].size;
    return ans + findSmallThan(a[k].R, p);
  }
  int findSmallThan(long long x) { return findSmallThan(root, heapNode(1, x)); }
  int findBigThan(int k, heapNode p) {
    if (k == -1) return 0;
    if (p >= a[k]) return findBigThan(a[k].R, p);
    int ans = 1;
    if (a[k].R != -1) ans += a[a[k].R].size;
    return ans + findBigThan(a[k].L, p);
  }
  int findBigThan(long long x) { return findBigThan(root, heapNode(1, x)); }
};
const int spfaEdgeNum = 5005;
const int spfaNodeNum = 2005;
struct spfaStruct {
  struct node {
    int v, w;
  };
  vector<node> g[N];
  long long dis[N];
  int inq[N], n;
  void init(int N) {
    n = N;
    int i;
    for (i = 0; i <= n; i++) g[i].clear(), d[i] = 0;
  }
  void add(int u, int v, int w = 1) {
    node p;
    p.v = v;
    p.w = w;
    g[u].push_back(p);
    d[v]++;
  }
  void spfa(int s) {
    int i;
    for (i = 1; i <= n; i++) dis[i] = inf, inq[i] = 0;
    dis[s] = 0;
    inq[s] = 1;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      inq[u] = 0;
      for (i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        int w = g[u][i].w;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          if (!inq[v]) Q.push(v), inq[v] = 1;
        }
      }
    }
  }
  long long f[N];
  int d[N];
  void DP() {
    int i;
    queue<int> Q;
    for (i = 1; i <= n; i++)
      if (!d[i]) Q.push(i);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        f[v] += f[u];
        if (--d[v] == 0) Q.push(v);
      }
    }
  }
};
struct fraction {
  long long a, b;
  fraction() {}
  fraction(long long x) {
    a = x;
    b = 1;
  }
  fraction(long long x, long long y) {
    a = x;
    b = y;
    deal();
  }
  void deal() {
    if (b < 0) b = -b, a = -a;
    long long k = Gcd(a, b);
    if (k < 0) k = -k;
    a /= k;
    b /= k;
  }
  fraction operator+(fraction p) {
    fraction ans;
    ans.b = Lcm(b, p.b);
    ans.a = ans.b / b * a + ans.b / p.b * p.a;
    ans.deal();
    return ans;
  }
  fraction operator-(fraction p) {
    fraction ans;
    ans.b = Lcm(b, p.b);
    ans.a = ans.b / b * a - ans.b / p.b * p.a;
    ans.deal();
    return ans;
  }
  fraction operator*(fraction p) {
    fraction ans;
    ans.a = a * p.a;
    ans.b = b * p.b;
    ans.deal();
    return ans;
  }
  fraction operator/(fraction p) {
    fraction ans;
    ans.a = a * p.b;
    ans.b = b * p.a;
    ans.deal();
    return ans;
  }
  int operator<(const fraction &p) const { return a * p.b < b * p.a; }
  int operator>(const fraction &p) const { return a * p.b > b * p.a; }
  int operator==(const fraction &p) const { return a * p.b == b * p.a; }
  int operator!=(const fraction &p) const { return a * p.b != b * p.a; }
};
const int mod = 1000000007;
const long long MAX = 1000000000000000000LL;
const int M = 3005;
int a[M][M];
char s[M][M];
int n, m, K;
int main() {
  RD(n, m, K);
  int i, j;
  for (i = 1; i <= n; i++) RD(s[i] + 1);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      if (s[i][j] != '.') {
        char c = s[i][j];
        if (c == 'R') {
          int x = j + i - 1;
          if (x > m) continue;
          a[i][x]++;
        } else if (c == 'L') {
          int x = j - (i - 1);
          if (x >= 1) a[i][x]++;
        } else if (c == 'U') {
          if (i & 1) a[i / 2 + 1][j]++;
        } else if (c == 'D') {
        }
      }
  for (i = n; i >= 1; i--)
    for (j = 1; j <= m; j++) {
      a[i - 1][j] += a[i][j];
    }
  for (i = 1; i <= m; i++) {
    if (i > 1) putchar(' ');
    printf("%d", a[1][i]);
  }
  puts("");
}
