Write a Python program, in a file called decode.py, to solve the following problem: A princess was lost in the woods and came across a castle with the door ajar. She went in and found no one inside the castle until she heard a terrifying roar and a big beast appeared in front of her. The beast said that he was actually a prince, but was cursed to become a beast and the princess could help break the curse if she could get a bottle of potion that was under the big banyan tree. The beast gave the princess a piece of paper which had an encoded message on it. The message contained 16 alphanumeric characters (aep2eappse4ctd7) that encoded the location of the big banyan tree; that is, the encoded message contained the direction and the walking distance needed (from the castle) to find the big banyan tree. Help the princess save the prince by decoding the message to find the direction and the walking distance needed to find the bottle of potion under the big banyan tree. The direction has only four characters and the distance is computed from the four digits contained in the message. To decode the message, use the following key: The direction the princess needs to go can be found by extracting the first character at the second position of the given message and then getting a character from every fourth position in the message thereafter (i.e., every fourth position relative to the second character's position). The distance (in paces) is computed by extracting digits from positions/locations that are 4 places away from the previous position (starting at the fourth character of the message) and finding the sum of all the digits. Given the message found as input; decode and output the decoded message. Note that the input message should be able to be changed as long as it following the encoding scheme as indicated by the decoding key, and remains as the same length. For example, if the prince moves to a different location, there could be a different message left such as: fwp3rep2kse1cts4 Sample input prompts, input and output for run 1 of the program (input shown in bold blue); Enter the message found: aep2eap6pse4ctd7 To find the potion, you need to travel east for 19 paces. Sample input prompts, input and output for run 2 of the program (input shown in bold blue): Enter the message found: fwp3rep2kselcts4 To find the potion. Vou need to travel west for 10 paces.