Restore Valid IPv4 Addresses

Problem: Generate Valid IPv4 Addresses

You are given a digit-only string s. List every valid IPv4 address that can be produced by inserting dots into this string.

An IPv4 address has exactly four dot-delimited decimal parts. Every part must meet these conditions:

• Its integer value falls within 0 through 255;
• A part cannot begin with 0 unless that entire part is exactly "0";
• Use every character from the original string once, without changing their order.

Write each valid address on its own line in lexicographic order. Produce no output when no valid address can be constructed.

Input

One line containing the string s.

Output

Print each valid IPv4 address on a separate line, ordered lexicographically.

Constraints

• 1 <= len(s) <= 20
• s consists exclusively of digits.

Example

Input:

1234

Output:

1.2.3.4

Explanation: Splitting after each digit is the only way to create four valid segments while preserving all characters.

Example

Input: 1234

Output: 1.2.3.4

Explanation: The four single-digit sections form the only valid IPv4 address for this input.