SPOJ Brasil

Um problema comum em estruturas de dados é determinar o percorrimento de uma árvore binária. Existem três maneiras clássicas de fazer isso:

Pré-ordem: Você deve visitar primeiro a raiz, depois a sub-árvore esquerda e por último a sub-árvore direita.
Em-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a raiz e por último a sub-árvore direita.
Pós-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a sub-árvore direita e por último a raiz.

Veja a figura abaixo:

    A
   / \
  B   D
 /   / \
C   E   F

O resultado do percurso em pré, em e pós-ordem é, respectivamente: ABCDEF, CBAEDF e CBEFDA. Neste problema, você deve computar o percurso em pós-ordem de uma árvore binária dados os seus percursos em-ordem e pré-ordem.

Entrada

O conjunto de entrada consiste de um número C ≤ 2000, que dá o número de casos de teste e C linhas, uma para cada caso de teste. Cada caso de teste começa com um número 1 ≤ N ≤ 52, o número de nós nessa árvore arbitrária. Depois, há duas cadeias de caracteres S1 e S2 que descrevem o resultado do percurso da árvore em pré-ordem e em-ordem. Os nós da árvore são rotulados com caracteres diferentes no intervalo a..z e A..Z. Os valores de N, S1 e S2 são separados por um espaço em branco.

Saída

Para cada conjunto de entrada, você deve imprimir uma linha contendo o percorrimento em pós-ordem da árvore correspondente.

Exemplo

Entrada:
3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF

Saída:
Yzx
cba
CBEFDA