Custom-Encoded String Decode

A legacy market data vendor compresses its symbol directory with a bespoke run-length scheme, and you have inherited the decoder. The spec, recovered from a fax, is short but exact.

An encoded string is a sequence of tokens with no separators. There are two token kinds:

• Repeat token: one or more digits, then ~, then one or more lowercase letters. The letter run extends until the next digit, the next ^, or the end of the input. The token emits the letter run repeated count times: 3~ab emits ababab.
• Shift token: ^ followed by exactly one digit 1-9. It emits a copy of the previous token's entire emission with every letter shifted forward in the alphabet by that digit, wrapping z back to a: after 3~ab emitted ababab, the token ^2 emits cdcdcd. The shifted copy becomes the new "previous emission", so shift tokens chain: each one shifts what the token immediately before it emitted.

The decoded output is the concatenation of every token's emission, in order. The input is always valid: it starts with a repeat token, counts are at least 1, and letter runs are non-empty.

Implement decode_feed(encoded) returning the decoded string.

Examples

decode_feed("3~ab")
# 'ababab'  (repeat "ab" three times)

decode_feed("2~ab^1")
# 'ababbcbc'  ("abab", then "abab" shifted by 1)

decode_feed("1~zq2~x")
# 'zqxx'  (letters end where the next count starts)

Constraints

• Encoded length up to \(10^4\); counts can be multi-digit (for example 12~q); decoded output stays under \(10^6\) characters.
• Only lowercase letters appear in runs; shifts wrap z to a.
• No cleverness required on speed, but your tokenizer must be exact: every hidden test is an edge of the grammar, not a bigger version of the examples.