using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace SO13389560Balancing
{
class Program
{
static void Main(string[] args)
{
string s = "~(a b (c) d (e f (g) h) i) j (k (l (m) n) p) q";
string pattern = @"(?<=~[(](?:[^()]*|(?<Depth>[(])|(?<-Depth>[)]))*)[a-z]";
s = Regex.Replace(s, pattern, "!");
Console.WriteLine(s);
//Console.ReadKey();
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CnVzaW5nIFN5c3RlbS5UZXh0Owp1c2luZyBTeXN0ZW0uVGV4dC5SZWd1bGFyRXhwcmVzc2lvbnM7CgpuYW1lc3BhY2UgU08xMzM4OTU2MEJhbGFuY2luZwp7CiAgICBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKQogICAgICAgIHsKICAgICAgICAgICAgc3RyaW5nIHMgPSAifihhIGIgKGMpIGQgKGUgZiAoZykgaCkgaSkgaiAoayAobCAobSkgbikgcCkgcSI7CiAgICAgICAgICAgIHN0cmluZyBwYXR0ZXJuID0gQCIoPzw9flsoXSg/OlteKCldKnwoPzxEZXB0aD5bKF0pfCg/PC1EZXB0aD5bKV0pKSopW2Etel0iOwogICAgICAgIAoKICAgICAgICAgICAgcyA9IFJlZ2V4LlJlcGxhY2UocywgcGF0dGVybiwgIiEiKTsKCiAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHMpOwogICAgICAgICAgICAvL0NvbnNvbGUuUmVhZEtleSgpOwogICAgICAgIH0KICAgIH0KfQo=