A sentence is represented as a sequence of words separated by exactly one space. There are no leading or trailing spaces, and each word contains only lowercase and uppercase English letters.

The sentence may be shuffled by attaching each word’s original 1-indexed position to the end of that word, then rearranging the words in any order.

For example, the sentence "Coding with Loopa is fun" could be shuffled into "fun5 Coding1 is4 Loopa3 with2" .

Given a shuffled sentence string s containing at most 9 words, restore and return the sentence in its original word order without the appended position digits.

Example 1:

Input: s = "fun5 Coding1 is4 Loopa3 with2"
Output: "Coding with Loopa is fun"
Explanation: Each word has a digit at the end that represents its original position.
'Coding1' belongs at position 1 
'with2' belongs at position 2 
'Loopa3' belongs at position 3 
'is4' belongs at position 4 
'fun5' belongs at position 5

Example 2:

Input: s = "perfect3 Practice1 makes2"
Output: "Practice makes perfect"
Explanation: The digit at the end of each word gives its original position. "Practice1" comes first, "makes2" comes second, and "perfect3" comes third.

Example 3:

Input: s = "Hello1"
Output: "Hello"
Explanation: the sentence contains only one word. Since Hello1 is already at position 1, we only remove the digit and return "Hello".

Constraints

2 <= s.length <= 200

s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.

The number of words in s is between 1 and 9.

Each word contains exactly one digit, and the digit appears at the end of the word.

The digits in s are unique and represent all positions from 1 to the number of words.

The words in s are separated by a single space.

s contains no leading or trailing spaces.

43. Restore Sentence Order