Назовём скобочную последовательность _идеальной_, если она образована некоторым количеством открывающих скобок, за которыми следует такое же количество закрывающих скобок. Глубиной идеальной скобочной последовательности назовём количество скобок какого-то одного вида в ней. Глубиной скобки назовём количество скобок того же вида, включая её саму, до ближайшего к ней края последовательности. Например, последовательность _(((())))_ имеет глубину 4, а скобки в ней имеют глубины 1, 2, 3, 4, 4, 3, 2 и 1 соответственно.
Очевидно, что любую скобочную последовательность можно преобразовать в идеальную (возможно, пустую), если удалить из неё некоторое количество скобок.
Вам дана скобочная последовательность, возможно, неидеальная. Для каждой скобки в этой последовательности требуется определить две величины:
Если какая-то скобка не входит ни в какую идеальную скобочную последовательность, которую можно было бы получить удалением некоторых скобок из исходной последовательности, обе величины будем считать равными 0.
В единственной строке записана скобочная последовательность s, состоящая только из открывающих и закрывающих скобок. Ее длина length(s) находится в пределах от 1 до 105.
В первой строке выведите length(s) чисел — ответы на первый вопрос задачи для каждой скобки.
Во второй строке выведите length(s) чисел — ответы на второй вопрос задачи для каждой скобки.
## Входные Данные
В единственной строке записана скобочная последовательность s, состоящая только из открывающих и закрывающих скобок. Ее длина length(s) находится в пределах от 1 до 105.
## Выходные Данные
В первой строке выведите length(s) чисел — ответы на первый вопрос задачи для каждой скобки.Во второй строке выведите length(s) чисел — ответы на второй вопрос задачи для каждой скобки.
## Примеры
Входные данные(()())Выходные данные1 2 2 2 2 12 2 2 2 2 2Входные данные))()(()(())())()((Выходные данные0 0 1 1 2 3 3 4 5 5 4 3 3 2 1 1 0 00 0 5 1 5 5 3 5 5 5 5 3 5 5 1 5 0 0
[samples]
**Definitions**
Let $ s = s_1 s_2 \dots s_n $ be a bracket sequence of length $ n $, where each $ s_i \in \{ \texttt{(}, \texttt{)} \} $.
For a bracket $ s_i $, define:
- **Ideal subsequence**: A subsequence of $ s $ of the form $ \texttt{(}^k \texttt{)}^k $ for some $ k \geq 0 $, obtained by deleting some brackets.
- **Belongs to an ideal subsequence**: A bracket $ s_i $ is said to belong to *some* ideal subsequence if there exists an ideal subsequence containing $ s_i $.
- **Depth of a bracket** $ s_i $: If $ s_i $ belongs to some ideal subsequence, then its depth is the number of matching brackets in that ideal subsequence from $ s_i $ to the nearest end of the subsequence (i.e., the position index within the ideal subsequence’s nesting level).
- **Ideal depth of $ s_i $**: The maximum possible depth of $ s_i $ over *all* ideal subsequences containing it.
- **Maximum nesting depth of $ s_i $**: The maximum depth of the ideal subsequence that contains $ s_i $, i.e., the total number of opening brackets in such an ideal subsequence.
If $ s_i $ does not belong to *any* ideal subsequence, both values are 0.
**Constraints**
- $ 1 \leq n \leq 10^5 $
- $ s_i \in \{ \texttt{(}, \texttt{)} \} $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each position $ i \in \{1, \dots, n\} $:
1. Compute $ d_i $: the **ideal depth** of $ s_i $ (maximum nesting level it can achieve in any ideal subsequence containing it), or 0 if it belongs to none.
2. Compute $ D_i $: the **maximum nesting depth** of the ideal subsequence containing $ s_i $ (i.e., the total number of opening brackets in such a subsequence), or 0 if it belongs to none.
Output two lines:
- First line: $ d_1, d_2, \dots, d_n $
- Second line: $ D_1, D_2, \dots, D_n $