class Solution {
 public:
  vector<string> ambiguousCoordinates(string S) {
    vector<string> ans;
    S = S.substr(1, S.length() - 2);

    for (int i = 1; i < S.length(); ++i)
      for (const string& x : splits(S.substr(0, i)))
        for (const string& y : splits(S.substr(i)))
          ans.push_back('(' + x + ", " + y + ')');

    return ans;
  }

 private:
  vector<string> splits(const string& S) {
    if (S.empty() || S.length() > 1 && S.front() == '0' && S.back() == '0')
      return {};
    if (S.back() == '0')
      return {S};
    if (S.front() == '0')
      return {"0." + S.substr(1)};

    vector<string> candidates{S};
    for (int i = 1; i < S.length(); ++i)
      candidates.push_back(S.substr(0, i) + '.' + S.substr(i));
    return candidates;
  }
};

class Solution {
  public List<String> ambiguousCoordinates(String S) {
    List<String> ans = new ArrayList<>();
    S = S.substring(1, S.length() - 1);

    for (int i = 1; i < S.length(); ++i)
      for (final String x : splits(S.substring(0, i)))
        for (final String y : splits(S.substring(i)))
          ans.add("(" + x + ", " + y + ")");

    return ans;
  }

  private List<String> splits(final String S) {
    if (S.isEmpty() || S.length() > 1 && S.charAt(0) == '0' && S.charAt(S.length() - 1) == '0')
      return new ArrayList<>();
    if (S.charAt(S.length() - 1) == '0')
      return new ArrayList<>(Arrays.asList(S));
    if (S.charAt(0) == '0')
      return new ArrayList<>(Arrays.asList("0." + S.substring(1)));

    List<String> res = new ArrayList<>(Arrays.asList(S));
    for (int i = 1; i < S.length(); ++i)
      res.add(S.substring(0, i) + "." + S.substring(i));
    return res;
  }
}

class Solution:
  def ambiguousCoordinates(self, S: str) -> List[str]:
    def splits(S: str) -> List[str]:
      if not S or len(S) > 1 and S[0] == S[-1] == '0':
        return []
      if S[-1] == '0':
        return [S]
      if S[0] == '0':
        return [S[0] + '.' + S[1:]]
      return [S] + [S[:i] + '.' + S[i:] for i in range(1, len(S))]

    ans = []
    S = S[1:-1]

    for i in range(1, len(S)):
      for x in splits(S[:i]):
        for y in splits(S[i:]):
          ans.append('(%s, %s)' % (x, y))

    return ans