Vasya has several phone books, in which he recorded the telephone numbers of his friends. Each of his friends can have one or several phone numbers.

Vasya decided to organize information about the phone numbers of friends. You will be given n strings — all entries from Vasya's phone books. Each entry starts with a friend's name. Then follows the number of phone numbers in the current entry, and then the phone numbers themselves. It is possible that several identical phones are recorded in the same record.

Vasya also believes that if the phone number a is a suffix of the phone number b (that is, the number b ends up with a), and both numbers are written by Vasya as the phone numbers of the same person, then a is recorded without the city code and it should not be taken into account.

The task is to print organized information about the phone numbers of Vasya's friends. It is possible that two different people have the same number. If one person has two numbers x and y, and x is a suffix of y (that is, y ends in x), then you shouldn't print number x. If the number of a friend in the Vasya's phone books is recorded several times in the same format, it is necessary to take it into account exactly once.

Read the examples to understand statement and format of the output better.


-----Input-----

First line contains the integer n (1 ≤ n ≤ 20) — number of entries in Vasya's phone books. 

The following n lines are followed by descriptions of the records in the format described in statement. Names of Vasya's friends are non-empty strings whose length does not exceed 10. They consists only of lowercase English letters. Number of phone numbers in one entry is not less than 1 is not more than 10. The telephone numbers consist of digits only. If you represent a phone number as a string, then its length will be in range from 1 to 10. Phone numbers can contain leading zeros.


-----Output-----

Print out the ordered information about the phone numbers of Vasya's friends. First output m — number of friends that are found in Vasya's phone books.

The following m lines must contain entries in the following format "name number_of_phone_numbers phone_numbers". Phone numbers should be separated by a space. Each record must contain all the phone numbers of current friend.

Entries can be displayed in arbitrary order, phone numbers for one record can also be printed in arbitrary order.


-----Examples-----
Input
2
ivan 1 00123
masha 1 00123

Output
2
masha 1 00123 
ivan 1 00123 

Input
3
karl 2 612 12
petr 1 12
katya 1 612

Output
3
katya 1 612 
petr 1 12 
karl 1 612 

Input
4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789

Output
2
dasha 2 23 789 
ivan 4 789 123 2 456

Difficulty: interview

Starter code:

Solutions:
n = int(input())

friends = dict()

for _ in range(n):
    line = input().strip().split()
    if line[0] not in friends:
        friends[line[0]] = set()
    for i in range(2, len(line)):
        friends[line[0]].add(line[i])

def order(S):
    S2 = [(len(e),e) for e in S]
    S2.sort()

    real = set()

    for i in range(len(S2)):
        d,e = S2[i]
        flag = True
        for j in range(i+1, len(S2)):
            x = S2[j][1]
            if x[-d:] == e:
                flag = False
                break
        if flag:
            real.add(e)
    return real

print(len(friends))
for f in friends:
    nums = order(friends[f])
    st = ' '.join(nums)
    print(f + ' ' + str(len(nums)) + ' ' + st)


n = int(input())
d = dict()
for i in range(n):
    a = input().split()
    if a[0] not in d:
        d[a[0]] = []
    for j in range(2, len(a)):
        a[j] = a[j][::-1]
    d[a[0]] += a[2:]
print(len(d))
for x in d:
    a = d[x]
    a.sort(reverse = True)
    ##print(a)
    b = [a[0]]
    for i in range(1, len(a)):
        if a[i - 1][:len(a[i])] != a[i]:
            b += [a[i]]
    for i in range(len(b)):
        b[i] = b[i][::-1]
    print(x, len(b), *b)


from collections import defaultdict
from sys import stderr

n = int(input())

friends = defaultdict(lambda: set())

for i in range(n):
    name, _, *numbers = input().split()
    for number in numbers:
        skip_number = False
        for old_number in list(friends[name]):
            if number.endswith(old_number):
                friends[name].remove(old_number)
            elif old_number.endswith(number):
                skip_number = True
        if not skip_number:
            friends[name].add(number)

print(len(friends))
for name in friends:
    print('{} {} {}'.format(name, len(friends[name]), ' '.join(friends[name])))


n = int(input())

def is_suffix(phone, p):
    if len(p) <= len(phone):
        return False
    return phone == p[-len(phone):]

def is_any_suffix(phone, phones):
    for p in phones:
        if is_suffix(phone, p):
            return True
    return False

from collections import defaultdict

name_map = defaultdict(list)
for i in range(n):
    entry = input().split()
    name = entry[0]
    num = int(entry[1])
    phones = entry[2:]
    name_map[name].extend(phones)

print(len(name_map))
for name in name_map:
    phones = name_map[name]
    final_phones = set()
    for phone in phones:
        if not is_any_suffix(phone, phones) and phone not in final_phones:
            final_phones.add(phone)
    print(name, len(final_phones), ' '.join(final_phones))


def print_arr(arr):
	for i in arr:
		print(i, "", end="")
	print()	


n = int(input())
d = {}
for _ in range(n):
	name, num, *numbers = input().split()
	if name in d:
		s = d[name]
	else:
		s = []	
	for nm in numbers:
		for i in s:
			if i.endswith(nm):
				state=1
				break
			if nm.endswith(i):
				s.remove(i)
		else:
			s.append(nm)
	d[name] = s
	
print(len(d))	
for name in d:
	print(name, len(d[name]), end=" ")
	print_arr(d[name])							

n = int(input())
d = {}
for i in range(n):
    s = [z for z in input().split()]
    name = s[0]
    count = int(s[1])
    for z in range(count):
        if name in d.keys():
            d[name].append(s[2 + z])
        else:
            d[name] = [s[2 + z]]
            
for k in d.keys():
    a = set(d[k])
    a = list(a)
    b = []
    for i in range(len(a)):
        f = False
        for j in range(len(a)):
            if i != j:
                if len(a[i]) <= len(a[j]):
                    if a[j][len(a[j]) - len(a[i]):] == a[i]:
                        f = True
                        break
        if f == False:
            b.append(a[i])
    d[k] = b
print(len(d))
for k in d.keys():
    print(k, end = ' ')
    print(len(d[k]), end = ' ')
    print(' '.join(d[k]))
                
            
    

n = int(input())
d = {}
for i in range(n):
    arr = input().split()
    name = arr[0]
    cnt = arr[1]
    arr = arr[2:]
    if name in d:
        for j in arr:
            d[name].append(j)
    else:
        d[name] = arr

print(len(d))
for name in list(d.keys()):
    print(name)
    d[name] = list(set(d[name]))
    ans = []
    for i in range(len(d[name])):
        le = len(d[name][i])
        for j in range(len(d[name])):
            if(i!=j and le < len(d[name][j]) and d[name][j][-le:] == d[name][i]):
                break
        else:
            ans.append(d[name][i])
    ans = set(ans)
    print(len(ans))
    for i in ans:
        print(i)
    


n = int(input())
dic = {}
for i in range(n):
    text = input().split()
    nam = text[0]
    if nam not in dic:
        dic[nam] = set()
    for elem in text[2 :]:
        dic[nam].add(elem)
# print(dic)
print(len(dic))
for nam, s in list(dic.items()):
    ls = []
    for e in s:
        add = True
        l = len(e)
        for j in s:
            if j != e and j[ -l : ] == e:
                add = False
                break
        if add:
            ls.append(e)
    print(nam, len(ls), *ls)




from sys import stdin, stdout

n = int(stdin.readline().rstrip())
nameDict = {}
for _ in range(n):
    s = stdin.readline().rstrip().split()
    name = s[0]
    if name not in nameDict:
        nameDict[name]=set()
    for number in s[2:]:
        nameDict[name].add(number)

for name in list(nameDict.keys()):
    rem=set()
    for no1 in nameDict[name]:
        for no2 in nameDict[name]:
            if no1==no2:
                continue
            l1 = len(no1)
            l2 = len(no2)
            if l1<l2 and no2[-l1:]==no1:
                rem.add(no1)
    for no in rem:
        nameDict[name].remove(no)

print(len(list(nameDict.keys())))
for name in list(nameDict.keys()):
    print(' '.join([name,str(len(nameDict[name]))]+list(nameDict[name])))


n = int(input())
directory = dict()
for _ in range(n):
    name, k, *nums = input().split()
    if name in directory:
        directory[name] += nums
    else:
        directory[name] = nums

print(len(directory.keys()))
for name in directory:
    nums = directory[name]
    nums.sort(key=len)
    new_list = []
    for ind, num in enumerate(nums):
        l = len(num)
        if all(_num[-l:] != num for _num in nums[ind + 1:]):
            new_list.append(num)
    print(name, len(new_list), *new_list)

n = int(input())

names = {}

for i in range(n):
    entry = input().split(' ')
    name, k, numbers = entry[0], int(entry[1]), entry[2:]
    if not names.__contains__(name):
        names[name] = numbers
    else:
        names[name] += numbers

for name in names:
    lst = sorted(names[name], key=len)
    i = 0
    while i < len(lst):
        letter = lst[i]
        for j in range(i+1, len(lst)):
            if lst[j].find(lst[i], (len(lst[j])-len(lst[i]))) >= 0:
                lst.remove(lst[i])
                i -= 1
                break
        i += 1
    names[name] = lst

print(len(names))
for name in names:
    print('%s %d '%(name, len(names[name])),end='')
    for ent in names[name]:
        print('%s '%ent, end='')
    print()

n = int(input())
p = {}
o = {}
for i in range(n):
    e = input().split()
    if not e[0] in p:
        p[e[0]] = []
    for x in e[2:]:
        p[e[0]].append((len(x), x[::-1]))
for i in p:
    for x in sorted(p[i])[::-1]:
        f = False
        if not i in o:
            o[i] = []
        for z in o[i]:
            f |= x[1]==z or (x[0]<len(z) and x[1]==z[:x[0]])
        if not f:
            o[i].append(x[1])
print(len(o))
for i in o:
    print(i + ' ' + str(len(o[i])) + ' ' + ' '.join(x[::-1] for x in o[i]))


import sys
import copy

cases = sys.stdin.readline()
my_input = []
for line in sys.stdin.readlines():
  my_input.append(line.strip().split(" "))


my_dict = dict()
for line in my_input:
  arr = []
  for i in range(2, len(line)):
    arr.append(line[i])
  if (line[0] in my_dict):
    my_dict[line[0]].update(arr)
  else:
    my_dict[line[0]] = set(arr)

for x in my_dict:
  values = my_dict[x]
  final_values = copy.deepcopy(values)
  for a in values:
    for b in values:
      if(a.endswith(b) and a != b and b in final_values):
        final_values.remove(b)
  my_dict[x] = final_values

print(len(my_dict))
for x in my_dict:
  print(str(x) + " " + str(len(my_dict[x])) +  " " + ' '.join(my_dict[x]))


n=int(input())
s=set()
arr=[]
a={}
for i in range(n):
    rr=list(map(str,input().strip().split(' ')))
    arr.append(rr)
for i in range(n):
    t=arr[i]
    s.add(t[0])
    try:
        p=a[t[0]]
        for j in range(2,2+int(t[1])):
            a[t[0]].append(t[j])
    except:
        p=t[2]
        a[t[0]]=[p]
        for j in range(3,2+int(t[1])):
            a[t[0]].append(t[j])

for ii in s:
    p=a[ii]
    p=list(set(p))
    
    for i in range(len(p)):
        if(p[i]!='-1'):
            tt=p[i]
            for j in range(len(p)):
                if(j!=i):
                    pp=p[j]
                    if(len(pp)>=len(tt)):
                        continue
                    else:
                        y=0
                        ans=0
                        for uu in range(len(tt)-len(pp),len(tt)):
                            if(tt[uu]!=pp[y]):
                                ans=1
                            y+=1
                        if(ans==0):
                            p[j]='-1'
    d=[]
    
    cnt=0
    for oo in p:
        if(oo!='-1'):
            cnt+=1
    d.append(cnt)

    for oo in p:
        if(oo!='-1'):
            d.append(oo)

    a[ii]=d
print(len(s))
for i in s:
    print(i,end=' ')
    t=a[i]
    for j in t:
        print(j,end=' ')
    print()



import math
import sys
import getpass
import bisect


def ria():
    return [int(i) for i in input().split()]


files = True

if getpass.getuser().lower() == 'frohe' and files:
    sys.stdin = open('test.in')
    # sys.stdout = open('test.out', 'w')

n = ria()[0]
nm = {}
for i in range(n):
    ar = [i.strip() for i in input().split()]
    name = ar[0]
    if not (name in nm):
        nm[name] = []
    for j in ar[2:]:
        nm[name].append(j)
for i in nm:
    nm[i] = sorted(nm[i], key=lambda x: len(x))

nmfin = {}
for i in nm:
    cur = nm[i]
    nmfin[i] = []
    for j in range(len(cur)):
        bad = False
        for j1 in range(j + 1, len(cur)):
            if cur[j1].endswith(cur[j]):
                bad = True

                break
        if not bad:
            nmfin[i].append(cur[j])
print(len(nmfin))
for i in nmfin:
    print(i,len(nmfin[i]), end=' ')
    for j in nmfin[i]:
        print(j,end=' ')
    print()


def same(x,y):
    if(len(x)>len(y)):
        if(y==x[len(x)-len(y):]):
            return 2
    else:
        if(x==y[len(y)-len(x):]):
            return 1
        else:
            return 0
    return 0

n=int(input())
pb=dict()
for i in range(n):
    record=input().split()
    if(record[0] in list(pb.keys())):
        pb[record[0]]+=record[2:]
    else:
        pb[record[0]]=record[2:]
for i in list(pb.keys()):
    rf=[]
    for j in pb[i]:
        flag=True
        for k in range(len(rf)):
            if(same(j,rf[k])==2):
                flag=False
                rf[k]=j
            elif(same(j,rf[k])==1):
                flag=False
        if(flag):
            rf.append(j)
    pb[i]=rf
print(len(list(pb.keys())))
for i in list(pb.keys()):
    print(i,len(pb[i]),*pb[i])
        


n = int( input() )

L = []

m = {}
names = []

for i in range( n ):
    a = input().split()

    name = a[0]
    names.append( a[0] )

    a = a[2:]

    if name not in m:
        m[ name ] = []

    for j in a:
        m[ name ].append( j )

names = set( names )

for i in names:

    #print( i )

    a = list( set(m[i] ) )
    #print( a )

    good = [True] * len(a)

    for j in range( len(a) ):
        for k in range( len(a) ):
            if j != k:
                if a[k].endswith( a[j] ):
                    good[j] = False
                    break

    ok = False
    cnt = 0
    for j in range( len(a) ):
        if good[j] == True:
            cnt += 1
            ok = True

    if ok == False:
        continue

    out = i + " " + str(cnt)

    for j in range( len(a) ):
        if good[j]:
            out += " " + a[j]

    L.append( out )

print( len(L) )
for i in L:
    print( i )


return


phones = dict()
n = int(input())

for i in range(n):
    name, num, *numbers = input().split()
    for number in numbers:
        try:
            for el in phones[name]:
                if el.endswith(number):
                    break
                if number.endswith(el):
                    phones[name].remove(el)
                    phones[name].add(number)
                    break
            else:
                phones[name].add(number)
        except KeyError:
            phones[name] = {number}

print(len(phones))
print('\n'.join([' '.join([name, ' '.join([str(len(numbers)), ' '.join(numbers)])]) for name, numbers in list(phones.items())]))



n = int(input())
book = {}
book_cool = {}
for i in range(n):
    li = list(input().split())
    if li[0] not in book:
        book[li[0]] = []
    for num in li[2:int(li[1]) + 2]:
        book[li[0]].append(num[::-1])
for name in book:
    t = book[name]
    t.sort()
    book_cool[name] = set()
    tt = book_cool[name]
    for i in range(1, len(t)):
        if t[i].startswith(t[i - 1]):
            pass
        else:
            tt.add(t[i - 1])
    tt.add(t[-1])
print(len(book_cool))
for i in book_cool:
    print(i, len(book_cool[i]), end = ' ')
    for j in book_cool[i]:
        print(j[::-1], end = ' ')
    print()
    

n=int(input())
a={}
for i in range(n):
    q=input().split()
    if q[0] in a:
        a[q[0]]+=q[2:]
    else:
        a[q[0]]=q[2:]
print(len(a))
for w in a:
    b=a[w]
    b.sort(key=lambda x:len(x))
    i=0
    while True:
        j=i+0
        while j!=len(b)-1:
            j+=1
            if b[i] == b[j][len(b[j])-len(b[i]):]:
                del b[i]
                break
        else:
            i+=1
        if i==len(b):
            break
    print(w,len(b),*b)



n = int(input())
d = dict()
for i in range(n):
    inp = input().split()
    name, cnt = inp[0], int(inp[1])
    d[name] = d.get(name, set())
    d[name].update(inp[2:])
print(len(d))
for k, v in d.items():
    v = list(v)
    for i in range(len(v)):
        for j in range(len(v)):
            if i != j and len(v[i]) <= len(v[j]) and v[j][len(v[j]) - len(v[i]):] == v[i]:
                v[i] = '-'
    l = 0
    for e in v:
        if e != '-':
            l += 1
    print(k, l, end=' ')
    for e in v:
        if e != '-':
            print(e, end=' ')
    print()


n = int(input())

book = dict()

for i in range(n):
    phones = []
    inp = [i for i in input().split()]

    name = inp[0]

    phones = [i for i in inp[2:]]

    for ph in phones:
        if not name in book:
            book[name] = [ph]
            continue
        f= True
        for j in range(len(book[name])):
            if len(book[name][j]) <= len(ph) and ph.rfind(book[name][j]) + len(book[name][j]) == len(ph):
                book[name][j] = ph
                break
            elif (len(book[name][j]) >= len(ph) and book[name][j].rfind(ph) + len(ph) == len(book[name][j])):
                f = False
        else:
            if f:
                book[name].append(ph)

print(len(book))
for name in book:
    print(name, len(book[name]), end=' ')
    for ph in book[name]:
        print(ph + '', end=' ')
    print()
    


def check(a, s1, s2):
    s1, s2 = str(s1), str(s2)
    #print(s1,s2)
    #print(s1[len(s1) - len(s2):len(s1)],s2)
    #print(s1[len(s1) - len(s2):len(s1)] == s2)
    #print()
    if s1[len(s1) - len(s2):len(s1)] == s2:
        return True
    elif s1 == s2 or not(s2 in a):
        return False
        



n = int(input())
name = []
phone = []

for i in range(n):
    a = list(input().split())
    #for i in range(int(a[1]) + 1):
        #a[i + 1] = int(a[i + 1])
    if not(a[0] in name):
        name.append(a[0])
        phone.append(a[2:2 + int(a[1])])
    else:
        phone[name.index(a[0])] += a[2:2 + int(a[1])]

ans = []
for i in range(len(phone)):
    phone[i] = list(set(phone[i]))
    ans.append([])

for i in range(len(phone)):
    for j in range(len(phone[i])):
        kek = 0
        for k in range(len(phone[i])):
            if j != k and check(ans[i],phone[i][k],phone[i][j]):
                kek += 1
        if kek == 0:
            ans[i].append(phone[i][j])

print(len(name))
for i in range(len(name)):
    print(name[i], len(ans[i]), *ans[i])


n=int(input())
d={}
for _ in range(n):
    a=input().split()
    if a[0] in d:
        for i in range(int(a[1])):
            d[a[0]].append(a[2+i])
        continue
    d[a[0]]=[]
    for i in range(int(a[1])):
        d[a[0]].append(a[2+i])
print(len(d))
for i in d:
    for j in range(len(d[i])):
        for k in range(len(d[i])):
            if j != k and d[i][k].endswith(d[i][j]):
                d[i][j]='a'
    print(i,len([e for e in d[i] if e!='a']),end=' ')
    for g in d[i]:
        if g!='a':
            print(g,end=' ')
    print()