Generate Valid IP Addresses

You are given a string s containing only digits. Your task is to generate all possible valid IP addresses by inserting exactly three dots into s.

An IP address is composed of four segments separated by dots, where each segment is an integer in the range \(0 \leq segment \leq 255\). A segment is considered valid if it does not contain leading zeros, except when the segment is exactly "0".

For example:

Input: 25525511135
Output:
255.255.11.135
255.255.111.35

Implement an algorithm to list all valid IP addresses that can be formed. If no valid IP addresses can be generated, output nothing.

inputFormat

The input is read from standard input and consists of a single line containing a string s of digits.

outputFormat

Print each valid IP address on a separate line in the order they are generated. If there are multiple valid IP addresses, output all of them; if none exist, output nothing.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>