1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/usr/bin/python3.9

from itertools import combinations
import functools


class dri:
    def __init__(self, s, len1=-1,n1=-1,len2=-1,n2=-1):
        #self.s = s
        if len1 == -1:
            self.val = 0
            self.min_val = 0
            self.calc_val(s)
            self.n = 0
            self.len = len(s)
            for i in range(self.len):
                self.n = self.n*2
                if s[i]=='L':
                    self.n = self.n + 1
        else:
            self.len = len1 + len2
            self.n   = n1*pow(2,len2) + n2

    def calc_val(self,s):
        self.min_val = 0
        self.val = 0
        for a in map(lambda x: 1 if x == 'L' else -1, s):
            self.val = self.val + a
            if (self.val < self.min_val):
                self.min_val = self.val

    def __eq__(self, d):
        return (self.len == d.len and self.n == d.n)

    def __hash__(self):
        return hash(self.n*1024+self.len)

    def print(self):
        print(self.s, end=" ")
        print("   val="+str(self.val), end=" ")
        print("   min_val="+str(self.min_val))


n = int(input())
drit = []
for i in range(n):
    s = input()
    drit.append(s)

dri_tab = [[] for i in range(n)]

for i in range(n):
    s = drit[i]
    st = set()
    for r in range(1, len(s)+1):
        for x in combinations(s, r):
            st.add("".join(x))
    for s in st:
        d = dri(s)
        if d.min_val >= d.val or d.val > 0:
            dri_tab[i].append(dri(s))


for i in range(n):
    for j in range(n):
        s = set()
        for d in dri_tab[i]:
            if d.val == 0:
                s.add(d)
        if (i!=j):
            for d in dri_tab[j]:
                if d.val == 0:
                    s.add(d)
        for dx in dri_tab[i]:
            for dy in dri_tab[j]:
                if dx.val >= 0 and dx.min_val >= 0 and dx.val + dy.val == 0:
                    s.add( dri(" ", dx.len, dx.n, dy.len, dy.n) )
        print(len(s),end="" if j == n-1 else " ")
    print()