using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Should be (): " + FixMissingParenthesis(")(", new List<int>(), new List<int>()));

        Console.WriteLine("Should be ()(): " + FixMissingParenthesis("()(", new List<int>(), new List<int>()));

        Console.WriteLine("Should be (()()): " + FixMissingParenthesis("(()(", new List<int>(), new List<int>()));

        Console.WriteLine("Should be aa(b)z: " + FixMissingParenthesis("a)a(b)z", new List<int>(), new List<int>()));

        Console.WriteLine("Should be z(a)(b): " + FixMissingParenthesis("z(a)(b", new List<int>(), new List<int>()));

        Console.WriteLine("Should be a(b)c(d): " + FixMissingParenthesis("a(b)c(d)", new List<int>(), new List<int>()));

        Console.WriteLine("Should be z(): " + FixMissingParenthesis("z()", new List<int>(), new List<int>()));

        Console.WriteLine("Should be (a(z())): " + FixMissingParenthesis("(a(z()))", new List<int>(), new List<int>()));

    }

    static string FixMissingParenthesis(string body, IList<int> leftParenthesis, IList<int> rightParenthesis, int index = 0, bool pass = true) 

    {

        if(index == body.Length) 

        {

            if(leftParenthesis.Count != rightParenthesis.Count)

                if(leftParenthesis.Count > rightParenthesis.Count)

                    while(leftParenthesis.Count > rightParenthesis.Count) 

                    {

                        rightParenthesis.Add(index);

                        body = body + ")";

                    }

                else

                   body = body.Remove(index-1, 1);

            return body;

        }

        if(body[index] == '(')

            leftParenthesis.Add(index);

        if(body[index] == ')')

        {

            rightParenthesis.Add(index);

            if(leftParenthesis.Count < rightParenthesis.Count) {

                body = body.Remove(index, 1);

            }

        }

        return FixMissingParenthesis(body, leftParenthesis, rightParenthesis, ++index);

    }

}