Description

A wavy number is a number that alternates between a pair of distinct digits, such as $1212121$. A double wavy number is a number that is wavy in two bases. For example, the decimal number $191919$ is wavy in base 10, and its base 11 representation $121212$ is also wavy, so the decimal number $191919$ is a double wavy number. In particular, a single-digit number also counts as a wavy number, e.g., $1$.

Similarly, we define triple wavy numbers as numbers that are wavy in three different bases, and even quadruple wavy numbers, e.g., $300_{(10)}=606_{(7)}=363_{(9)}=454_{(8)}=1\mathtt{A}1_{(13)}$, where the subscript denotes the base. Your task is to find, within the specified ranges, all double, triple, or quadruple wavy numbers.

Input Format

A single line contains five space-separated decimal integers $l, r, L, R, k$. The interval $[l, r]$ denotes the range of bases to consider, the interval $[L, R]$ denotes the range of numbers to consider, and $k$ specifies the multiplicity of wavy numbers to find.

Output Format

Output, in increasing order and in decimal, all wavy numbers within the specified range that have the specified multiplicity. Print one number per line.

10 11 190000 960000 2

191919
383838
575757
767676
959595

Hint

Constraints

For all testdata, it is guaranteed that $2 \le l \le r \le 32$, $1 \le L \le R \le 10^7$, and $k \in \{2, 3, 4\}$.

Translated by ChatGPT 5