Restore IP Addresses

Given a string s consisting solely of digits, insert three dots into it to form all possible valid IP addresses. A valid IP address is written as four integers separated by dots. Each integer must satisfy \(0 \leq x \leq 255\) and cannot have leading zeros unless the number is exactly 0.

For example, when the input is "25525511135", the two valid IP addresses are:

• 255.255.11.135
• 255.255.111.35

Your task is to generate all valid IP addresses from the given string and print each address on a separate line. If no valid IP addresses exist, print nothing.

inputFormat

The input consists of a single line containing a non-empty string of digits.

outputFormat

Print each valid IP address on a new line. If there are no valid IP addresses, output nothing.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>