In this 3 Palindrome, Given an input string word, split the string into exactly 3 palindromic substrings. Working from left to right, choose the smallest split for the first substring that still allows the remaining word to be split into 2 palindromes.Similarly, choose the smallest second palindromic substring that leaves a third palindromic substring.If there is no way to split the word into exactly three palindromic substrings, print “Impossible” (without quotes). Every character of the string needs to be consumed.Cases not allowed –After finding 3 palindromes using above instructions, if any character of the original string remains unconsumed.No character may be shared in forming 3 palindromes.Constraints:Constraints1 <= the length of input sting <= 1000InputFirst line contains the input string consisting of characters between [a-z].OutputPrint 3 substrings one on each line.Example:Example 1InputnayannamantenetOutputnayannamantenetExplanation:The original string can be split into 3 palindromes as mentioned in the output.However, if the input was nayanamantenet, then the answer would be “Impossible”.