Theory: Pump a word

See what pumping does to a word.

What to build

A program that prints x yᵏ z for k = 0, 1, …, m.

Requirements

  • Print one word per line, starting with k = 0.
  • Treat the token ε as the empty string, and print ε for an empty result.

Input

Three lines: x, y and z (each possibly ε). Line 4: m.

Output

m + 1 lines.

Constraints

Each part has at most 10 symbols; 0 ≤ m ≤ 5.

Example

Input:

a
b
c
2

Output:

ac
abc
abbc

Why it works

Pumping repeats the loop part y of the word; k = 0 removes it entirely.

Examples

Example 1 · Input
a
b
c
2
Expected output
ac
abc
abbc
Example 2 · Input
ε
ab
ε
2
Expected output
ε
ab
abab

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

x + y * k + z repeats y k times.

Hint 2

Read ε as the empty string, and print ε when the result is empty.

Solution

Show one correct solution (try it yourself first)
def part(token):
    return "" if token == "ε" else token


x, y, z = part(input()), part(input()), part(input())
m = int(input())
for k in range(m + 1):
    print(x + y * k + z or "ε")

Lesson: Beyond regular: the pumping lemma →