eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Прямий, центрований та обернений порядок

Прямий, центрований та обернений порядок

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Однією з класичних задач на структури даних є порядок обходу вершин бінарного дерева. Існує три стандартні варіанти обходу:

Прямий: відвідується корінь, ліве піддерево, праве піддерево;Центрований: відвідується ліве піддерево, корінь, праве піддерево;Обернений: відвідується ліве піддерево, праве піддерево, корінь;

Розглянемо рисунок:

prb1513

При прямому, центрованому та оберненому обході ми отримаємо відповідно ABCDEF, CBAEDF та CBEFDA. В задачі необхідно знайти послідовність вершин при оберненому обході, якщо відомі прямий та центрований.

Вхідні дані

Перший рядок містить кількість тестів c (c2000). Кожний наступний рядок є окремим тестом та містить кількість вершин у бінарному дереві n (1n52) та два рядки S[1] та S[2], що містять відповідно прямий та центрований обхід дерева. Вершини дерева пронумеровані різними символами з множин a..z та A..Z. Значення n, S[1] та S[2] розділені пропуском.

Вихідні дані

Для кожного тесту вивести послідовність вершин при оберненому обході дерева.

Приклад

Вхідні дані #1
3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF
Вихідні дані #1
Yzx
cba
CBEFDA