Restore IP Addresses

Given a string of digits, restore all possible valid IP addresses by inserting dots into the string. An IP address consists of four segments separated by dots. Each segment is an integer in the range (0) to (255) and must not have leading zeros (except for the number zero itself). For example, if (s = "25525511135"), the valid addresses are (255.255.11.135) and (255.255.111.35).

inputFormat

The input consists of a single line containing a string (s) composed of digits.

outputFormat

Print each valid IP address on a separate line in the order they are generated by the algorithm.## sample

25525511135

255.255.11.135
255.255.111.35