Restore IP Addresses

Given a string s containing only digits, generate all possible valid IP addresses by inserting three dots into the string. An IP address is defined as four integers separated by dots, i.e., in the form \(a.b.c.d\), where each integer \(a, b, c, d\) is in the range \(0 \leq x \leq 255\). Additionally, each segment must not contain leading zeros unless the segment itself is "0".

Note: The length of the input string must be between 4 and 12 (inclusive). If it does not meet these criteria or no valid segmentation exists, the output should be empty.

Examples:

• Input: "25525511135" → Output: "255.255.11.135" and "255.255.111.35"
• Input: "0000" → Output: "0.0.0.0"

inputFormat

The input consists of a single line containing a string s composed only of digits. This string does not include any spaces or additional characters.

Input Format: s

outputFormat

Output all possible valid IP addresses that can be obtained by inserting three dots into the string. Each valid IP address should be printed on a separate line. If no valid IP addresses can be formed, output nothing.

Output Format: Each line should contain one valid IP address.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>