Sweeping a Keypad Lock

A door has a keypad whose keys are the characters of the string keys. The lock keeps only the last n keys pressed and opens the moment they spell the secret code, so a long run of presses tests many codes at once: after pressing 0 1 1 0 on a lock with n = 3, the codes 011 and 110 have both been tried.

A locksmith wants to try every possible code of length n with as few presses as possible. Write keypad_sweep(keys, n) that returns the presses as a string of exactly len(keys)**n + n - 1 characters (no shorter sequence can work) in which every one of the len(keys)**n codes appears as a block of n consecutive presses. Any such string is accepted.

Examples

Input:  keys = "01", n = 3
Output: "0001011100"   (one of several valid answers)
Explanation: 10 presses; the blocks 000 001 010 101 011 111 110 100 are all 8 codes.

Input:  keys = "abc", n = 2
Output: "aabacbbcca"   (one of several valid answers)

Input:  keys = "x", n = 4
Output: "xxxx"

Constraints

• 1 <= len(keys) <= 10, and the characters of keys are distinct
• 1 <= n and len(keys)**n <= 10**5, so the answer can be about 100 000 characters long

Goals

• Turn a covering-sequence problem into a walk that uses every edge of a graph once
• Run a depth-first walk with an explicit stack so long walks do not overflow the call stack