Strawberry Carrot Watermelon Chamoe Melon Game

Didi's favorite random game ~! Which game ~! Game start!!

Strawberry carrot watermelon chamoe melon game♪

At Didi University the strawberry carrot watermelon chamoe melon game runs by these rules.

1. Fix the number of words $n$ and the number of beats $b$. The number of beats is greater than or equal to the number of words, and the same word may appear several times.
2. Choose the $n$ words $S_1, S_2, \ldots, S_n$ that the game uses.
3. On turn $i$, shout the words exactly as the code below prints them.

if (b == 1) printf("%s", S[1]);
else {
    if ((i - 1) % (2 * (b - 1)) + 1 < b) {
        for (int j = 1; j <= (i - 1) % (b - 1) + 1; j++)
            printf("%s ", S[(j - 1) % n + 1]);
    } else {
        for (int j = 1; j <= b - ((i - 1) % (b - 1)); j++)
            printf("%s ", S[(j - 1) % n + 1]);
    }
}

The word set $S$ is numbered from 1.

With $n = 3$, $b = 5$ and the words king, god, gd in that order, the turns go like this.

1. king
2. king god
3. king god gd
4. king god gd king
5. king god gd king god
6. king god gd king
7. king god gd
8. king god
9. king
10. king god

The same pattern continues after that.

Didi wonders which turn holds the moment the word $k$ has been shouted $X$ times. Write a program that answers Didi's question.

The first line contains $n$ and $b$. ($1 \le n \le 2 \times 10^5$, $n \le b \le 10^{12}$)

The second line contains a word $k$ and $X$. ($1 \le X \le 10^{12}$)

The third line contains the $n$ words of the game, separated by spaces. Every word consists of lowercase letters and is at most 10 characters long.

Print the number of the turn in which the word $k$ is shouted for the $X$-th time. Only inputs that have an answer are given.