题目描述

如果一个数在某进制下的表示（至少三位）形如 $ababa\dots$，即数字交替出现，我们称之为交替数。例如 $212121$、$797979$、$A4A4A4A4$ 分别是十进制、十进制和十六进制下的交替数。

如果一个十进制数在多个不同的进制下都是交替数，就称它为多阶交替数。具体地，若它在 $k$ 个不同的进制下都是交替数，就称它为 $k$ 阶交替数。例如十进制数 $10$，二进制表示为 $1010$（四位交替），三进制表示为 $101$（三位交替），所以 $10$ 是一个二阶交替数。

现在给定一个进制范围 $[a, b]$、一个十进制数范围 $[x, y]$ 以及目标阶数 $k$，请你找出所有满足条件的 $k$ 阶交替数：该数在 $[a, b]$ 中的至少 $k$ 个不同进制下都是交替数，且十进制值在 $[x, y]$ 范围内。按十进制值从小到大的顺序每行输出一个。

注意：交替数至少是三位数（即进制表示的长度至少为 $3$），且数字交替要求从最高位开始，相邻两位数字不同，并且整个数的数字规律为 $c_1c_2c_1c_2\dots$ 的形式（第一位与第三位、第五位……相同，第二位与第四位……相同，第一位与第二位不同）。

输入格式

一行，五个整数 $a, b, x, y, k$，分别表示进制范围下界、上界、十进制值范围下界、上界和目标阶数。保证 $2 \le a \le b \le 36$，$1 \le x \le y \le 10^6$，$k \in \{2, 3, 4\}$。

输出格式

每行一个十进制整数，表示一个满足条件的 $k$ 阶交替数。按十进制值从小到大输出。如果不存在，则无输出。

样例

9 10 1 200 2

191

样例解释
十进制数 $191$ 在九进制下表示为 $232$（交替数），在十进制下表示为 $191$（交替数），因此在进制范围 $[9,10]$ 内是两个进制的交替数，满足二阶要求，且值在 $[1,200]$ 内。

数据范围

• $2 \le a \le b \le 36$
• $1 \le x \le y \le 10^6$
• $k \in \{2, 3, 4\}$