30186번 - 괄호 댄스

문제

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

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

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

서현이는 아름다움에 대한 자신만의 심오한 기준에 따라 다음 조건들을 만족해야 아름다운 공연이라고 생각한다.

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

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

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

아직 무대의 크기를 정확히 모르는 서현이를 도와 공연장의 크기가 1ドル,ドル 2ドル,ドル $\cdots,ドル $\lfloor\frac{N}{2}\rfloor$인 경우에 각각 아름다운 공연의 아름다움을 구하자.

입력

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

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

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

출력

$\lfloor\frac{N}{2}\rfloor$개의 줄에 걸쳐서 문제의 답을 출력한다.

$i$번째 줄에는 공연장의 크기가 $i$일 때의 아름다운 공연의 아름다움을 출력하며, 공연을 진행하는 것이 불가능할 경우 NO를 출력한다.

제한

힌트