Известный алхимик Шу Такер специализируется на создании химер. Известно, что «рецепты» (алгоритмы создания) химер кодируются правильными скобочными последовательностями.

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

• пустая строка является базовым рецептом;
• если $$$t_1$$$ и $$$t_2$$$ — два рецепта химер, то новую химеру можно получить их объединением; ее рецептом будет конкатенация рецептов $$$t_1 t_2$$$ (второй рецепт, выписанный сразу за первым);
• если $$$t$$$ — рецепт химеры, то другую химеру можно получить алхимическим преобразованием с рецептом $$$\text{\texttt{(}}\ t\ \text{\texttt{)}}$$$;
• любая другая последовательность, которую нельзя получить с помощью описанных правил, не является рецептом химеры.

Так, например, «(()(()))» получается алхимией из «()(())», которая, в свою очередь, получается объединением из химер «()» и «(())». Обе из них получаются из базового пустого рецепта алхимией.

Рецепт последнего достижения Шу Такера, разговаривающей химеры, можно представить как правильную скобочную последовательность $$$s$$$ длины $$$n$$$. Это несомненно потрясающее достижение, и рецепт строго засекречен, однако у Эдварда и Альфонса есть определенные сомнения на счет использованных материалов...

Эдвард может делать запросы формата «? $$$l$$$ $$$r$$$», и на каждый такой запрос узнавать, является ли отрезок рецепта $$$s_l s_{l+1} \ldots s_r$$$ правильной скобочной последовательностью. Иными словами, если выписать только символы $$$s$$$ с $$$l$$$-го по $$$r$$$-й включительно, будет ли полученная скобочная последовательность удовлетворять данному выше определению.

Не превышая разрешенное число запросов, полностью раскройте секретный рецепт $$$s$$$.