34507번 - Scary Subsequences 다국어

문제

In this problem, all strings consist only of four characters: a, b, c, and d.

Busy Beaver has three strings $x,ドル $y,ドル and $z$ that he's really scared of. In particular, he only likes strings that are not a subsequence of any of them.

Answer $Q$ queries. In query $i,ドル you are given a string $s_i,ドル such that $x,ドル $y,ドル and $z$ are all subsequences of $s_i$ and $|s_i| > \max(|x|, |y|, |z|)$. Help Busy Beaver find the length of the shortest subsequence of $s_i$ that is not a subsequence of any of $x,ドル $y,ドル or $z$.

¹A string $s$ is a subsequence of a string $t$ if $s$ can be obtained from $t$ by deleting some (possibly none or all) characters from $t,ドル without reordering the remaining characters.

입력

The first three lines of the input contain the strings $x,ドル $y,ドル and $z$ (1ドル \le |x|, |y|, |z| \le 60$), consisting of characters a, b, c, d.

The next line contains a single positive integer $Q$ (1ドル \le Q \le 1.5 \cdot 10^5$).

The next $Q$ lines each contain a string, the $i$-th of which is $s_i$ ($\max(|x|, |y|, |z|) < |s_i| \leq 3 \cdot 10^5$), consisting of characters a, b, c, d such that $s_i$ has $x,ドル $y,ドル and $z$ as subsequences.

The sum of $|s_i|$ over all queries does not exceed 3ドル \cdot 10^5$.

출력

On the $i$-th line, output a single positive integer --- the shortest possible length of a subsequence of $s_i$ that is not a subsequence of any of $x,ドル $y,ドル or $z$.

제한

노트

In the first query, all length 1ドル$ subsequences of abcbc are subsequences of one of $x,ドル $y,ドル or $z,ドル but the subsequence cb is not, so the answer is 2ドル$.

In the second query, d is a subsequence of dabcabc that is not a subsequence of any of $x,ドル $y,ドル or $z$.

In the third query, bbc is a subsequence of abbcc that is not a subsequence of any of $x,ドル $y,ドル or $z,ドル and it is the shortest such subsequence.