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();
        }
    }
}