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