You are given a string word consisting of lowercase English letters, and a list of strings...

You are given a string word consisting of lowercase English letters, and a list of strings skeletons consisting of '.' characters and lowercase English letters. Every skeleton will always be the same length as word.

Your task is to return a list of skeletons that can form the given word. A skeleton can form a word if all characters can be replaced with other characters taken from the same skeleton to make the string equal to the word. If no strings within skeletons can form the given word by doing this, return an empty list. The matching skeletons should be returned in the same order they appear in skeletons and the list of skeletons may not all be unique.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than O(skeletons.length × word.length²) will fit within the execution time limit.

Constraints

• [execution time limit] 0.5 seconds (cpp)
• [memory limit] 1 GB
• [input] string word
  • A word string consisting of English lowercase letters.
  • Guaranteed constraints: 0 < word.length < 100
• [input] array.string skeletons
  • An array of strings consisting of '.' characters and lowercase English letters.
  • Guaranteed constraints: 1 ≤ skeletons.length ≤ 100, skeletons[i].length = word.length

Example

Input:

word = "hello"
skeletons = ["he-lo", "he--o", "-ell-", "hello"]

Output:

["he-lo", "he--o", "hello"]

Explanation:

• "he-lo" is a skeleton of "hello" as they already match.
• "he--o" is a skeleton of "hello" because the two '.' characters can be replaced with 'e' and 'l' respectively.
• "-ell-" is not a skeleton of "hello" because the first '.' would need to be 'h' and the last '.' would need to be 'o', but the skeleton has 'l' at position 3 which doesn't match 'l' at position 3 in "hello".
• "hello" is a skeleton of "hello" as they already match.