괄호 댄스

SNUPC 폐막 공연의 하이라이트는 괄호 댄스이다. 괄호 댄스를 위해 총 $N$개의 괄호가 무대 뒤에 일렬로 줄을 서서 연습하고 있다. 각 괄호는 여는 괄호 또는 닫는 괄호 중 하나이다.

공연 담당자인 서현이는 공연 30분 전에야 무대가 너무 좁아 괄호 $N$개를 모두 넣을 수 없다는 사실을 알게 되었다. 공연장의 크기가 $K$일 때, 서현이는 괄호들의 순서를 바꾸지 않고 정확히 $2K$개의 괄호를 골라 공연장에 내보내려 한다. 고른 괄호들이 원래 배열에서 연속일 필요는 없다.

각 괄호에는 아름다움을 의미하는 정수 $A_1, A_2, \cdots, A_N$이 있다. $A_i$는 음수일 수도 있다.

서현이는 다음 조건을 만족해야 아름다운 공연이라고 생각한다.

• 선택한 괄호들을 앞에서부터 읽었을 때 올바른 괄호 문자열이 되어야 한다.
• 공연의 아름다움은 선택한 괄호들의 아름다움의 합이며, 이 값이 가능한 한 최대가 되어야 한다.

올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. 문자열 X가 올바른 괄호 문자열이면 (X)도 올바른 괄호 문자열이다.
3. 문자열 X와 Y가 올바른 괄호 문자열이면 XY도 올바른 괄호 문자열이다.
4. 위 규칙으로 만들 수 없는 문자열은 올바른 괄호 문자열이 아니다.

첫째 줄에 문자열의 길이 $N$이 주어진다. ($2 \leq N \leq 200\,000$)

둘째 줄에 현재 괄호들의 배열을 나타내는 (와 )로 이루어진 문자열 $S$가 주어진다. $S$는 올바른 괄호 문자열이 아닐 수도 있다.

셋째 줄에 각 괄호의 아름다움을 나타내는 정수 $A_1, \cdots, A_N$이 공백으로 구분되어 주어진다. ($-10^{8} \le A_i \le 10^{8}$)

$\lfloor\frac{N}{2}\rfloor$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 공연장의 크기가 $i$일 때 아름다운 공연의 아름다움을 출력한다. 공연을 진행하는 것이 불가능하면 NO를 출력한다.