Description

Last time you helped Orange Cat complete his puzzles. This time, he wants to arrange these puzzles on his shelf.

Each puzzle can be represented by a string composed of digits from 0 to 9. Since the orange cat has a special preference for multiples, he defines a function f(s, x, m) which counts how many substrings of length m in string s representing numbers that are multiples of x.

Now give you n puzzles p₁ ~ p_n, for each string s_i, calculate f(s_i, x₁, m), f(s_i, x₂, m), ..., f(s_i, x_k, m) and sort the strings according to the following priority:

1. Sort by the value of f(s_i, x₁, m), larger values come first
2. If f(s_i, x₁, m) values are equal, compare f(s_i, x₂, m), and so on
3. If all values up to f(s_i, x_k, m) are equal, maintain their original relative positions

Divisibility Rules for numbers 2 through 4 (You may also use alternative methods.):
2: The last digit is even.
3: The sum of all digits is divisible by 3.
4: The last two digits form a number divisible by 4.

Input

The first line contains three positive integers n, m, k.

The second line contains k positive integers x₁ ~ x_k

The following n lines each contain a string s_i.

Constraints

• 1 <= n <= 1000
• 1 <= | s_i |, m <= 100
• | s₁ | = | s₂ | = ... = | s_n |
• 1 <= k <= 3
• 2 <= x_i <= 4
• All strings contain only 0 ~ 9

Subtasks

• testcases 1 ~ 6: m = | s₁ |, k = 1, x₁ = 2
• testcases 7 ~ 8: m = | s₁ |, k = 2, x₁ = 2, x2 = 3
• testcases 9 ~ 10: m = | s₁ |, k = 3, x₁ = 2, x₂ = 3, x₃ = 4
• testcases 11 ~ 12: k = 1, x₁ = 2
• testcases 13 ~ 14: k = 2, x₁ = 2, x₂ = 3
• testcases 15 ~ 16:  k = 3, x₁ = 2, x₂ = 3, x₃ = 4

Output

Output n lines, where the i-th line contains a string representing the puzzle placed in the i-th position.

Please remember to print "\n" at the end, and dont print space (" ") at the end of every line

Hint1:
Please implement string swapping in bubble sort using strcpy to avoid TLE (Time Limit Exceeded).

Hint2:
The meaning of k in this problem is:
k = 1: You only need to compare the number of multiples of 2
k = 2: You need to first compare multiples of 2, if equal, then compare multiples of 3
k = 3: Following this pattern, compare in priority order of multiples of 2, 3, and 4

Sample Input  Download

Sample Output  Download

Tags

Discuss