Encryption

题号：NC237289
时间限制：C/C++/Rust/Pascal 7秒，其他语言14秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

You are given a string $s$ of lowercase letters and let $\text{count}(t)$ be the number of occurrences of $t$ in $s$ , we define an encryption function $f(t)$ as follows:
$f(t_1t_2 \dots t_m) = \begin{cases} t_1 + f(t_2 \dots t_m) &,\; m > 1 \;\text{and}\; \text{count}(f(t_2 \dots t_m)) \equiv 0\pmod 2 \\ f(t_2 \dots t_m) + t_1 &,\; m > 1 \;\text{and}\; \text{count}(f(t_2 \dots t_m)) \equiv 1 \pmod 2\\ t_1 &,\; m = 1, \end{cases}$
where ' $+$ ' means string concatenation, for example, $ab+cd=abcd$ .
For each query string $t$ , please calculate $f(t)$ .

输入描述:

The first line contains a string $s(1 \leq |s| \leq 10^6)$ of lowercase letters.
The second line contains an integer $q$ $(1 \leq q \leq 10^6)$ indicating the number of queries.
For the next $q$ lines, each line contains a nonempty lowercase query string $t$ .
It is guaranteed that the sum of the length of all queries doesn't exceed $10^6$ .

$10^6$

输出描述:

For each query, output the encrypted result in a single line.

示例1

输入

复制

ababa
1
aba

输出

复制

aab