G - K-nacci Operations 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 575 点

問題文

a, b からなる K 個の文字列 S_1, S_2, \ldots, S_K が与えられます。また、i > K なる整数 i に対し、文字列 S_i を S_{i-1}, S_{i-2}, \ldots, S_{i-K} をこの順に連結した文字列として定めます。

あなたは、文字列 T に対して以下の操作を行います。

  • |S_N| を S_N の長さとして、j = 1, 2, \ldots, |S_N| に対し以下の操作を順に行う。
    • S_N の j 文字目が a のとき、T の先頭の文字を末尾に移動させる。
    • S_N の j 文字目が b のとき、T 全体を反転させる。すなわち、T の文字の並びを逆にする。

一連の操作を終えた後の文字列 T を求めてください。

制約

  • 2 \leq K \leq 100
  • K は整数
  • S_i は a, b からなる空でない文字列 (1 \leq i \leq K)
  • S_1, S_2, \ldots, S_K の長さの和は 2 \times 10^5 以下
  • 1 \leq N \leq 10^{18}
  • N は整数
  • T は英小文字からなる長さ 1 以上 2 \times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

K
S_1
S_2
\vdots
S_K
N
T

出力

答えを出力せよ。

入力例 1

3
a
aa
b
5
abc

出力例 1

cab

S_1 = a、S_2 = aa、S_3 = b、S_4 = baaa、S_5 = baaabaa です。

操作によって文字列 T は abc → cba → bac → acb → cba → abc → bca → cab と変化するため、一連の操作を終えた後の文字列 T は cab となります。

入力例 2

2
a
ba
6
fibonacci

出力例 2

canobific

入力例 3

5
aba
a
bb
ba
aab
1000000000000000000
abcba

出力例 3

aabcb

Score : 575 points

Problem Statement

You are given K strings S_1, S_2, \ldots, S_K consisting of a and b. Also, for an integer i > K, define the string S_i as the concatenation of S_{i-1}, S_{i-2}, \ldots, S_{i-K} in this order.

You perform the following operation on a string T.

  • Perform the following operations for j = 1, 2, \ldots, |S_N| in order, where |S_N| is the length of S_N.
    • If the j-th character of S_N is a, move the first character of T to the end.
    • If the j-th character of S_N is b, reverse T entirely. That is, reverse the order of the characters of T.

Find the string T after the series of operations.

Constraints

  • 2 \leq K \leq 100
  • K is an integer.
  • S_i is a non-empty string consisting of a and b. (1 \leq i \leq K)
  • The sum of the lengths of S_1, S_2, \ldots, S_K is at most 2 \times 10^5.
  • 1 \leq N \leq 10^{18}
  • N is an integer.
  • T is a string consisting of lowercase English letters with length between 1 and 2 \times 10^5, inclusive.

Input

The input is given from Standard Input in the following format:

K
S_1
S_2
\vdots
S_K
N
T

Output

Output the answer.

Sample Input 1

3
a
aa
b
5
abc

Sample Output 1

cab

S_1 = a, S_2 = aa, S_3 = b, S_4 = baaa, and S_5 = baaabaa.

Through the operations, the string T changes as abc → cba → bac → acb → cba → abc → bca → cab, so the string T after the series of operations is cab.

Sample Input 2

2
a
ba
6
fibonacci

Sample Output 2

canobific

Sample Input 3

5
aba
a
bb
ba
aab
1000000000000000000
abcba

Sample Output 3

aabcb