a = []
n, target = "", ""
while 1:
    try:
        a.append(input())
        if len(a[-1]) == 1:
            n = a[-1]
            target = input()
            break
    except:
        break
sign = [x for x in target if x < n]
for num in a[:-1]:
    tmp = [m for m in num if m < n]
    if ''.join(sign) in ''.join(tmp):
        print(num)

while 1:
    try:
        l, r = input().split(';')
        ans = 0

        # 将字符串拆分为（字母、数字、空格）组与（标点符号）组
        a, b = "", ""
        for c1 in l:
            if '0' <= c1 <= '9' or 'a' <= c1 <= 'z' or 'A' <= c1 <= 'Z' or c1 == ' ':
                a += c1
            else:
                b += c1
        c, d = "", ""
        for c2 in r:
            if '0' <= c2 <= '9' or 'a' <= c2 <= 'z' or 'A' <= c2 <= 'Z' or c2 == ' ':
                c += c2
            else:
                d += c2
        a, c = list(a.lower().split()), list(c.lower().split())
        m, n = len(a) + 1, len(c) + 1

        # 编辑距离
        dp = [[0] * n for _ in range(m)]
        for x in range(n):
            dp[0][x] = x
        for y in range(m):
            dp[y][0] = y
        for i in range(1, m):
            for j in range(1, n):
                if a[i - 1] == c[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1, dp[i - 1][j] + 1)

        ans += dp[-1][-1]
        for x, y in zip(b, d):
            if x != y:
                if x == '?' or y == '?':
                    ans += 1
        ans += abs(len(b) - len(d))
        print("(" + str(ans) + "," + str(max(len(a) + len(b), len(c) + len(d))) + ")")

    except:
        break

while 1:
    try:
        m, n = map(int, input().split())
        dp = [[0.0] * (n + 1) for _ in range(m + 1)]
        a = []
        for _ in range(m):
            a.append(list(map(float, input().split())))  # a[i][3*j:3*j+2]为向下、向右、原地的概率
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i == m - 1 and j == n - 1:
                    continue
                dp[i][j] = (dp[i + 1][j] * a[i][3 * j] + dp[i][j + 1] * a[i][3 * j + 1] + 1) / (
                        1.0 - a[i][3 * j + 2])  # 从终点往回走，倒推
        print(dp[0][0])
    except:
        break