Valid IP Address Generation

Given a string containing only digits, your task is to generate all possible valid IPv4 addresses that can be formed by inserting three dots into the string. An IPv4 address contains four octets, each of which must be an integer in the range \(0\) to \(255\), inclusive. Moreover, no octet (except for \(0\) itself) should have leading zeros.

For example, for the input 25525511135, the valid IP addresses would be 255.255.11.135 and 255.255.111.35.

The output should list the valid IP addresses in lexicographically sorted order. If no valid IP addresses can be generated, output nothing.

inputFormat

The input consists of a single line containing a string N of digits.

outputFormat

Print each valid IP address on a separate line in lexicographically sorted order. If there are no valid IP addresses, do not output anything.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>