Valid IP Address Splits

You are given a string of digits ip. Return every way to split it, in order and using every digit exactly once, into a valid IP address of the form A.B.C.D.

A split is valid when:

• it uses every digit of ip, in order, split into exactly four parts
• each part is 1 to 3 digits long
• each part's value, read as a number, is between 0 and 255
• no part starts with 0 unless the part is exactly "0"

Return the valid IP addresses in sorted order. If no split is valid, return an empty list.

Examples

Example 1

Input: ip = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2

Input: ip = "0000"
Output: ["0.0.0.0"]

Example 3

Input: ip = "1111"
Output: ["1.1.1.1"]