?Adreuqse arap atierid
time limit per test
1 segundo
memory limit per test
256 megabytes
input
entrada padrão
output
saída padrão

A codificação de caracteres Útil desde Cuneiforme até Siríaco (UCS) ou Unicode é uma invenção fenomenal que atualmente é desenvolvida em conjunto com o Instituto de Organização de Símbolos (ISO). O objetivo é possibilitar que todo tipo de símbolo e sistema de escrita que é de uso comum em todo o mundo hoje ou no passado seja representável nos computadores.

Esse esforço tem alguns desafios em seu caminho, sendo que um deles é que existem linguagens como o Árabe, o Hebreu e o Siríaco que escrevem da direita para a esquerda, sendo que os nossos computadores são habituados a entender as coisas da esquerda pra direita. O Consórcio do Unicode, para resolver tais problemas, criou alguns símbolos especiais e alguns algoritmos para que computadores entendam textos bidirecionais. Tome por exemplo este texto que mistura português e hebreu:

A ordem em que os caracteres são guardados é totalmente diferente da ordem em que eles são renderizados. Observe a ordem em que esses caracteres ficam na memória:

E também note que alguns caracteres como os parênteses são renderizados invertidos, isto porque eles tem um significado especial: Parênteses que abrem e fecham, e não parênteses esquerdos e direitos.

O funcionamento se baseia em caracteres fortes, fracos e neutros.

A divisão de anúncios da Elogog (empresa famosa da Nlogônia) está pensando em fazer um navegador de Internet e precisa da sua ajuda para certificar que os textos sejam renderizados corretamente!

Considere que caracteres fortes alteram a direção do texto da posição atual até o próximo caractere forte (ou o final do texto) e que caracteres fracos e neutros não alteram a direção do texto.

Input

A primeira linha contém um inteiro $$$N$$$ $$$(1 \le N \le 10^6)$$$ que representa o tamanho da linha a ser convertida.

A segunda linha é de tamanho $$$N$$$ com caracteres restritos a um subconjunto do conjunto ASCII. O alfabeto é composto por caracteres neutros: espaços simples, vírgulas, pontos, parênteses (), colchetes [], chaves {} e parênteses angulares <>; caracteres fracos: números e operadores matemáticos +, -, *, / e =; caracteres fortes: letras latinas minúsculas, que representam um texto em uma linguagem esquerda para direita, e letras latinas maiúsculas, que representam texto em uma linguagem direita para esquerda.

O primeiro caractere da linha é sempre um caractere forte.

Output

Imprima uma linha de tamanho $$$N$$$ na ordem de renderização.

Examples

Input
44
portugues 1 2 3 ( UERBEH 1 234 ( 5 portugues
Output
portugues 1 2 3 ( 5 ) 234 1 HEBREU portugues
Input
75
os SOD) SEBARA numeros SOCIBARA como 123), MAICINI da ->. LAUGI E 1234 SAM.
Output
os ARABES (DOS numeros ARABICOS como 123), INICIAM da ->. MAS 1234 E IGUAL.
Input
79
equacoes [+54SETNEREFID OAS [100 = +12+34. mas ([ADNIA ([SALE, sao S}A)D]IL<AV.
Output
equacoes [+54+12+34 = 100] SAO DIFERENTES. mas ([ELAS]) AINDA, sao VA>LI[D(A{S.