Problem H
Pearls

Laura likes to create pretty necklaces with pearls. She has two neckalces $A$ and $B$, which she would like to use as templates to create a new necklace. A necklace is represented by a string, where each character represents the color of a bead on the necklace.

Laura furthermore has a group of $k$ colour pairs $S_1, \cdots , S_ k$ that she really doesn’t like because they’re ugly in that colour and order, so she attempts to avoid them when creating her new necklace.

Laura will create her new necklace in a particular way. For each pearl in necklace $A$ from the start, she is going to combine its colour with the colour of each of the pearls from necklace $B$.

For each pearl in necklace $A$, $A_ i$, she looks at each pearl in necklace $B$, $B_ j$. If the combination $A_ iB_ j$ is not an ugly combination, she puts pearls of colour $A_ iB_ j$ at the end of her new necklace. If it is an ugly combination, she does nothing. Note that Laura only looks for ugly combinations when constructing the necklace, not after they have been added to the new necklace.

Help Laura determine what her new neckalce is going to look like. Laura has $q$ questions, where the $i$’th one, $t_ i$ asks for the colour of the $t_ i$’th pearl on the new necklace.

Input

The first line contains four integers $L_ A, L_ B, k$ and $q$. These are the length of $A$, the length of $B$, the number of ugly combinations and the number of questions resepctively.

The next line contains the string $A$, consisting of exactly $L_ A$ characters from the set $[a-z]$.

The next line contains the string $B$, consisting of exactly $L_ B$ characters from the set $[a-z]$.

The next $k$ lines contain the ugly combinations, one combination per line. These combinations are written as strings containing exactly 2 characters from the set $[a-z]$, separated with a single space.

The next $q$ lines are the positions for which Laura wants to know the color of the bead in the final necklace. 0 is the first position in the necklace.

Output

Output should contain $q$ lines, each containing a single character from the set $[a-z]$, representing the answers to Laura’s questions in the same order they were given.

Constraints

$1 \le L_ A, L_ B \le 2\cdot 10^5$
$1 \le q \le 10^5$
$0 \le k < 26^2$
All queries refer to a valid position in the final necklace.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 1:

Laura creates the necklace ac ac bc bc cc cc bc bc (spaces inserted for ease of reading). No ugly terms were removed.

Explanation of Sample 2:

Laura creates the necklace ca cc ba ac ac (spaces inserted for ease of reading). The terms bc, aa and aa were removed because they are ugly.

4 2 1 2
abcb
cc
c a
3
12

c
b

4 2 2 2
cbaa
ac
b c
a a
7
7

c
c