딸기당근수박참외메론게임

디디가 좋아하는 랜덤 게임 ~! 무슨 게임 ~! 게임 스타트!!

딸기당근수박참외메론게임♪

디디대학에서 하는 딸기당근수박참외메론게임의 규칙은 다음과 같다.

1. 게임에 쓸 단어의 수 $n$과 박자 수 $b$를 정한다. 박자 수는 단어의 수보다 크거나 같아야 하고, 같은 단어가 여러 번 들어가도 된다.
2. 정한 $n$에 맞춰 사용할 단어 $S_1, S_2, \ldots, S_n$을 정한다.
3. $i$번째 차례에는 아래 코드가 출력하는 것과 똑같이 단어를 외친다.

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]);
    }
}

단어 집합 $S$의 번호는 1부터 시작한다.

$n = 3$, $b = 5$이고 단어가 순서대로 king, god, gd이면 차례마다 외치는 말은 다음과 같다.

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

그 뒤로도 같은 방식으로 이어진다.

디디는 단어 $k$가 외쳐진 횟수가 $X$번이 되는 순간이 몇 번째 차례인지 궁금해졌다. 디디의 궁금증을 풀어 줄 프로그램을 작성하라.

첫째 줄에 $n$과 $b$가 주어진다. ($1 \le n \le 2 \times 10^5$, $n \le b \le 10^{12}$)

둘째 줄에 단어 $k$와 $X$가 주어진다. ($1 \le X \le 10^{12}$)

셋째 줄에 게임에 쓸 단어 $n$개가 공백으로 구분되어 주어진다. 모든 단어는 알파벳 소문자로 이루어지고, 길이는 10을 넘지 않는다.

단어 $k$가 $X$번째로 외쳐지는 차례의 번호를 출력한다. 정답이 존재하는 입력만 주어진다.