Sort Strings by Weighted Sum

Given a list of 26 integers representing the weights for the letters 'a' to 'z', and a list of n strings (each composed of only lowercase letters), your task is to sort the strings in increasing order of their weighted sum. The weighted sum of a string is defined as

\(\displaystyle \sum_{i=1}^{|s|} w(s_i)\)

where \(w(s_i)\) is the weight of the letter at position i, determined by the corresponding value in the weights array.

In case of ties (i.e. two strings having the same weighted sum), maintain the original order as in the input.

inputFormat

The input is read from standard input (stdin) and consists of:

• The first line contains 26 space-separated integers representing the weights for letters 'a' to 'z'.
• The second line contains an integer n, which is the number of strings.
• The next n lines each contain a string of lowercase letters.

outputFormat

Output the sorted list of strings to standard output (stdout), with each string printed on a new line.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
5
abb
abc
abcd
aaa
bcc

aaa
abb
abc
bcc
abcd