35255번 - Pearls 서브태스크다국어

Laura likes to create pretty necklaces with pearls. She has two necklaces $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.

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 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.

• $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.