Restore IP Addresses

You are given a string s containing only digits. Your task is to restore all possible valid IPv4 addresses that can be formed by inserting three dots into s. An IPv4 address consists of four octets separated by dots. Each octet must satisfy the following conditions:

• It is a number between 0 and 255 (inclusive).
• If it has more than one digit, it should not start with a '0'.

Mathematically, if a segment is denoted by \( x \), then \( 0 \le x \le 255 \) and if \( x \) has two or more digits then the following holds: \( x[0] \neq '0'\).

Your solution should read the input from standard input (stdin) and write the output to standard output (stdout). For each valid IP address, print it on a separate line. The order of the output does not matter.

Note: If no valid IP addresses can be formed, output nothing.

inputFormat

The input consists of a single line containing the string s composed of digits. The length of s is between 0 and 12.

outputFormat

Output each valid IP address on a separate line. If no valid IP addresses exist, output nothing.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>