Уилл застрял в Обратной стороне, но он все еще может общаться со своей мамой, Джойс, используя гирлянду (он может включать и выключать ее силой мысли). Он не может напрямую сказать маме, где он, потому что монстр, который унес его на Обратную сторону, узнает и спрячет его в другое место.

Поэтому он придумал задачу, чтобы сообщить маме свои координаты. Его координаты будут ответом на эту задачу.

Строка, состоящая только из скобок ('(' и ')'), называется скобочной последовательностью. Некоторые скобочные последовательности называются правильными скобочными последовательностями. Более формально:

• Пустая строка является правильной скобочной последовательностью.
• Если s является правильной скобочной последовательностью, то (s) тоже является правильной скобочной последовательностью.
• Если s и t являются правильной скобочной последовательностью, то st (конкатенация s и t) тоже является правильной скобочной последовательностью.

Строка, состоящая из скобок и знаков вопроса ('?') называется красивой, если и только если есть способ заменить каждый из знаков вопроса на '(' или ')' так, чтобы получившаяся строка была непустой правильной скобочной последовательностью.

Уилл сообщил маме строку s, состоящую из скобок и знаков вопроса (используя код Морзе и гирлянду), его координаты равны числу пар чисел (l, r) таких, что 1 ≤ l ≤ r ≤ |s|, а строка s_ls_l + 1... s_r является красивой, где s_i — i-й символ строки s.

Джойс ничего не знает о скобочных последовательностях, поэтому она просит у вас помощи.