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

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

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

디디대학에서의 딸기당근수박참외메론게임의 룰은 다음과 같은 규칙으로 진행된다.

1. 게임에 쓰일 단어의 수 n과 박자 수 b를 정한다. 단, 박자수는 단어의 수보다 크거나 같아야 하며, 같은 단어가 여러 번 들어갈 수 있다.
2. 앞서 정한 n만큼, 사용할 단어(S₁, S₂, ..., S_n)를 정한다.
3. 각 i(1, 2, ...) 차례마다 단어들을 아래 코드와 같은 결과로 말해야 한다.

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, 집합 S = {king, god, gd}일 때,

• king
• king god
• king god gd
• king god gd king
• king god gd king god
• king god gd king
• king god gd
• king god
• king
• king god
• ...

각 차례마다 위와 같은 순서대로 말해야한다.

디디는 문득 게임내에서 임의의 단어 k가 외쳐진 횟수가 X번째가 될 때, 그 차례가 몇번 째 인지 궁금해지기 시작했다. 그런 디디의 궁금증을 해결해 줄 프로그램을 작성하라.

첫째 줄에 n(1 ≤ n ≤ 2 × 10⁵)과 b(n ≤ b ≤ 10¹²)가 주어진다.

둘째 줄에는 임의의 단어 k와 X(1 ≤ X ≤ 10¹²)가 주어진다.

셋째 줄에는 게임에 쓰일 단어 n개가 공백으로 구분되어 주어진다. 모든 단어는 알파벳 소문자로 구성되어 있으며, 각 단어의 길이는 10을 넘지 않는다.

문제의 정답을 출력하라. 정답이 항상 존재하는 경우만 입력으로 주어지는 것이 보장된다.