As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him. 

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:
 -  Empty string is a correct bracket sequence. -  if *s* is a correct bracket sequence, then (*s*) is also a correct bracket sequence. -  if *s* and *t* are correct bracket sequences, then *st* (concatenation of *s* and *t*) is also a correct bracket sequence. 
A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string *s* consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (*l*, *r*) such that 1 ≤ *l* ≤ *r* ≤ |*s*| and the string *s*<sub class="lower-index">*l*</sub>*s*<sub class="lower-index">*l* + 1</sub>... *s*<sub class="lower-index">*r*</sub> is pretty, where *s*<sub class="lower-index">*i*</sub> is *i*-th character of *s*.

Joyce doesn't know anything about bracket sequences, so she asked for your help.
The first and only line of input contains string *s*, consisting only of characters '(', ')' and '?' (2 ≤ |*s*| ≤ 5000).
For the first sample testcase, the pretty substrings of *s* are:
 1.  "(?" which can be transformed to "()". 1.  "?)" which can be transformed to "()". 1.  "((?)" which can be transformed to "(())". 1.  "(?))" which can be transformed to "(())". 
For the second sample testcase, the pretty substrings of *s* are:
 1.  "??" which can be transformed to "()". 1.  "()". 1.  "??()" which can be transformed to "()()". 1.  "?()?" which can be transformed to "(())". 1.  "??" which can be transformed to "()". 1.  "()??" which can be transformed to "()()". 1.  "??()??" which can be transformed to "()()()".
((?))
4
??()??
7
?????)(???
21
()()((?(()(((()()(())(((()((())))(()))(()(((((())))()))(((()()()))))))(((((()))))))))
62
))((()(()((((()))())()())((())())(((()()(())))))((())()()(()()(())()))()()(()()()(((()(()(()(()))))(
88
????????????????????????????????????????????????????????????????????????????????????????????????????
2500
)(
0
?(
0
??
1
)?(??((???????()?(?????????)??(????????((?)?????)????)??????(?????)?)?????)??????(??()??????)????????)?)()??????????????())????????(???)??)????????????????????(?????)??)???)??(???????????????)???)??)?
8314
()
1
(?
1
import os, time
a = []


def show_menu():
    os.system('cls')
    print("The Current Text Is : ")
    for line in range(len(a)):
        print(line + 1, ": ", a[line])
    print()
    print("Choose What You Want To Do")
    print("0.Exit")
    print("1.Write")
    print("2.Copy And Paste")
    print("3.Cut And Paste")
    print("4.Search")



def isvalid(cmd):
    return cmd in ['0', '1', '2', '3', '4', '5']


def write():
    print("Type The String You Want To Add To The Text: ")
    global a
    text = input()
    a.append(text)
    return "Nicely Done"


def copy_and_paste():
    print("Type The Interval Of The Lines You Want To Copy : ")
    global a
    try:
        l, r = map(int, input().split())
    except:
        return "Invalid Interval"
    l -= 1
    r -= 1
    if l > r or l < 0 or r >= len(a):
        return "Invalid Interval"
    b = []
    for i in range(l, r + 1):
        b.append(a[i])
    print("Type The Line You Want To Paste The Copied Lines : ")
    try:
        x = int(input())
    except:
        return "Invalid Line For Pasting"
    x -= 1
    if x < 0 or x > len(a):
        return "Invalid Line For Pasting"
    a = a[:x] + b + a[x:]
    return "Nicely Done"



def cut_and_paste():
    print("Type The Interval Of The Lines You Want To Cut : ")
    global a
    try:
        l, r = map(int, input().split())
    except:
        return "Invalid Interval"
    l -= 1
    r -= 1
    if l > r or l < 0 or r >= len(a):
        return "Invalid Interval"
    b = []
    for i in range(l, r + 1):
        b.append(a[i])
    c = a[:l] + a[r + 1:]
    print("After Cutting The Text Is : ")
    for line in range(len(c)):
        print(line, " ", c[line])
    print()
    print("Type The Line You Want To Paste The Cut Lines : ")
    try:
        x = int(input())
    except:
        return "Invalid Line For Pasting"
    x -= 1
    if x < 0 or x > len(c):
        return "Invalid Line For Pasting"
    a = c[:x] + b + c[x:]
    return "Nicely Done"


def search():
    print("Type The String You Want To Search In The Text")
    s = input()
    for str in a:
        if s in str:
            return "Found"
    return "Not Found"


def go_to_hell():
    print("Have A good Day !")
    time.sleep(3)
    exit()


def main():
    while True:
        show_menu()
        cmd = input()
        if not isvalid(cmd):
            print("Invalid Command")
            continue
        if cmd == '0':
            go_to_hell()
        if cmd == "1":
            print(write())
        if cmd == "2":
            print(copy_and_paste())
        if cmd == "3":
            print(cut_and_paste())
        if cmd == "4":
            print(search())
        time.sleep(2)


main()