Description

Bob and Alice are very interested in cryptography.
They always encrypt their messages when communicating with each other.
Unfortunately, Bob lost the program to decrypt messages because of the Windows Update yesterday. Therefore, he needs to decrypt the words by himself.

Now, Bob receives N strings (S1,S2...SN) from Alice in lexicographical order. He wants to know which of them have the same pattern as a certain string P and the frequency of such strings.
With these information, Bob can find out the original string by some dark magic.

Can you help discover all pairs (Si,Fi), where Si has the same pattern as P, and Fi is the frequency of Si where Fi > 0?

Note:

1. Two strings Si and P have the same pattern if and only if we can obtain P by replacing corresponding letters in Si, and vice versa. 

For example:

• Si = “abcb” and P = “theh” have the same pattern

  replace ‘a’ by ‘t’: S = "tbcb"
  replace ‘b’ by ‘h’: S = "thch"
  replace ‘c’ by ‘e’: S = “theh”

• Si = “abcb” and P = “ther” have different patterns

  It’s impossible to replace ‘b’ by both ‘h’, ‘r’

• Si = “abcb” and P = “thhh” have different patterns

  replace ‘a’ by ‘t’: S = "tbcb"
  replace ‘b’ by ‘h’: S = "thch"
  replace ‘c’ by ‘h’: S = “thhh”
  ‘b’ and ‘c’ should not be the same after replacement.

2. The frequency F of a string is its number of occurrences within the N strings (S1,S2...SN).

Ex: if Bob receives {“a”, “b”, “a”}

• F of “a” = 2 (S1,S3 = “a”)
• F of “b” = 1 (S2 = “b”)

Input

An integer N and a string P on the first line.
The next N lines give S1,S2...SN in lexicographical order.

• 0 ≤ |N| ≤ 5000
• 1 ≤ |Si|, P ≤ 5000, ∀i∈1,2,...N
• Si and P contain only lower-case English letters.

Output

Print on the first line the number M of distinct strings (from S1,S2...SN) that have the same pattern as P.
On the following M lines, print the (S,F) pair for the M strings that have the same pattern as P, one pair per line, in decreasing order of their frequencies. When the frequencies tie, please use the lexicographical order of the strings.
Remember ‘\n’ on the end of line.

Explanation of the sample I/O

There’re 5 kinds of strings {“fiv”, “oaq”, “aaa”, “fivqv”, “six”}.
Only “fiv”, “oaq”, “six” have the same pattern as “the”.

• frequency of “fiv” = 3
• frequency of “oaq” = 1
• frequency of “six” = 1

There’re 3 pairs (“fiv”, 3), (“oaq”, 1), (“six”, 1).
Print them by the rule above:

3
fiv 3
oaq 1
six 1

 

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss