import itertools
def next_balanced_parens(s):
num_pairs = len(s)//2
depth = 0
for i in range(len(s)-1, -1, -1):
if s[i] == ")":
depth += 1
else:
assert s[i] == "("
depth -= 1
if depth > 0:
break
else:
return "(" * (num_pairs+1) + ")" * (num_pairs+1)
left = s[:i] + ")"
l = num_pairs - left.count("(")
r = num_pairs - left.count(")")
return left + "("*l + ")"*r
def iter_balanced_parens():
s = ""
while True:
yield s
s = next_balanced_parens(s)
last = None
for s in itertools.islice(iter_balanced_parens(), 100):
if last is None or last < s or len(last) < len(s):
print(s)
else:
print(s, "lexicographic ordering error!")
last = s
aW1wb3J0IGl0ZXJ0b29scwoKZGVmIG5leHRfYmFsYW5jZWRfcGFyZW5zKHMpOgogICAgbnVtX3BhaXJzID0gbGVuKHMpLy8yCiAgICBkZXB0aCA9IDAKICAgIGZvciBpIGluIHJhbmdlKGxlbihzKS0xLCAtMSwgLTEpOgogICAgICAgIGlmIHNbaV0gPT0gIikiOgogICAgICAgICAgICBkZXB0aCArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYXNzZXJ0IHNbaV0gPT0gIigiCiAgICAgICAgICAgIGRlcHRoIC09IDEKICAgICAgICAgICAgaWYgZGVwdGggPiAwOgogICAgICAgICAgICAgICAgYnJlYWsKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuICIoIiAqIChudW1fcGFpcnMrMSkgKyAiKSIgKiAobnVtX3BhaXJzKzEpCgogICAgbGVmdCA9IHNbOmldICsgIikiCiAgICBsID0gbnVtX3BhaXJzIC0gbGVmdC5jb3VudCgiKCIpCiAgICByID0gbnVtX3BhaXJzIC0gbGVmdC5jb3VudCgiKSIpCiAgICByZXR1cm4gbGVmdCArICIoIipsICsgIikiKnIKCmRlZiBpdGVyX2JhbGFuY2VkX3BhcmVucygpOgogICAgcyA9ICIiCiAgICB3aGlsZSBUcnVlOgogICAgICAgIHlpZWxkIHMKICAgICAgICBzID0gbmV4dF9iYWxhbmNlZF9wYXJlbnMocykKCmxhc3QgPSBOb25lCmZvciBzIGluIGl0ZXJ0b29scy5pc2xpY2UoaXRlcl9iYWxhbmNlZF9wYXJlbnMoKSwgMTAwKToKICAgIGlmIGxhc3QgaXMgTm9uZSBvciBsYXN0IDwgcyBvciBsZW4obGFzdCkgPCBsZW4ocyk6CiAgICAgICAgcHJpbnQocykKICAgIGVsc2U6CiAgICAgICAgcHJpbnQocywgImxleGljb2dyYXBoaWMgb3JkZXJpbmcgZXJyb3IhIikKICAgIGxhc3QgPSBz