Description

Denny just learned the sorting method in school.

Sorting once is too easy for him, so the teacher asked a question that needs to be sorted twice to test him.

In this question, you will get N strings of length 6, you need to sort the strings internally according to a ~ z, and then sort the N strings in dictionary order.

 

For example:

N = 2

S₁ = abcabc, S₂ = ababab

Internally sorted string: S₁ = aabbcc, S₂ = aaabbb

The sorted string after sorting: aaabbb aabbcc

Input

The first line contains a integer N, the number of strings you need to sort

The following line contains N strings S₁ ~ S_N

For all testcase:

1 <= N <= 100

Output

The Output contains only one line, the sorted string after sorting.

note: remember to add a '\n' in the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A substring S' of a given string S with length N is a contiguous sequence of N letters from S.
For instance, the substrings with length 2 of “abcde” are “ab”, “bc”, “cd”, “de”.

Given a string S and an integer N together with another string P.
Your task is to find all substrings from S with length N that have the same pattern as P, and the frequencies of these substrings.

In this problem, the patterns of two strings A, B are the same if and only if the numbers of each kind of letters in A, B are equal.
For example:

• A = “ouo”, B = “oou” have the same pattern

  number of letter	a~n	o	p~t	u	v~z
  A = “ouo”	0	2	0	1	0
  B = “oou”	0	2	0	1	0

• A = “pap”, B = “oao” have different patterns

  number of letter	a	b~n	o	p	q~z
  A = “pap”	1	0	0	2	0
  B = “oao”	1	0	2	0	0

Moreover, under a given N, the frequency of a substring S' is its number of occurrences within all resulting substrings of S.
For example: S = “ababa”, S' = “aba”

• all substrings with length 3 = {“aba”, “bab”, “aba”}
• frequency of S' = 2

 

Hint:
To efficiently check if a substring S' and P have the same pattern as required by this problem: 

1. use two 1D arrays to record the numbers of each kind of letters in S' and P, respectively; 
   • ​​Just like the example above. TP[0] = the number of ‘a’ in P, TP[1] = the number of ‘b’ in P, and so on
2. check if each pair of corresponding elements in the two 1D arrays are equal. 

Input

One string S and an integer N on the first line.
Another string P on the second line.

• 1 ≤ N ≤ 3,000
• 1 ≤ |S|, |P| ≤ 3,000
• S, P contain only lower-case English letters.

Output

Print on the first line the number M of distinct substrings of S with length N that have the same pattern as P.

On the following M lines, print the (S', F') pair for the M substrings that have the same pattern as P, where F' is the frequency of S', one pair per line, in decreasing order of their frequencies. When the frequencies tie, please use the lexicographical order of the substrings.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss