Restore IP Addresses

You are given a string s containing only digits. Your task is to return all possible valid IP addresses that can be formed by inserting dots into s. An IP address is valid if it consists of four integers (each integer is between 0 and 255) separated by dots, and no integer (except 0) has leading zeros.

For example, given the input "25525511135", the valid IP addresses are "255.255.11.135" and "255.255.111.35" (order does not matter).

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

Note: Any valid ordering of the results is acceptable, but for the purpose of evaluation the addresses are expected to be printed in lexicographical order.

The algorithm can be implemented using backtracking. Use the following constraints:

• The input is read from standard input (stdin).
• The output should be printed to standard output (stdout).

The mathematical validity condition for a segment seg can be expressed as:

$$\text{Valid}(seg) = \begin{cases} \text{true} & \text{if } 0 \leq \text{int}(seg) \leq 255 \text{ and } (seg = "0" \text{ or } seg\text{ does not start with } '0') \\ \text{false} & \text{otherwise} \end{cases} $$

inputFormat

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

Example:

25525511135

outputFormat

Output each valid IP address on a new line, sorted in lexicographical order. If no valid IP addresses can be formed, output nothing.

## sample

25525511135

255.255.11.135
255.255.111.35

</p>