e-olymp
Задачи

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

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

Одной из классических задач на структуры данных является порядок обхода вершин бинарного дерева. Существуют три стандартных вариантов обхода:

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

Рассмотрим рисунок:

prb1513

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

Входные данные

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

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF
Выходные данные
Yzx
cba
CBEFDA