题目描述

形如 $ababa$ 的数，我们称之为交替数。不同的进制中都可能存在交替数，例如$212121、797979、A4A4A4A4$。 有一类特殊交替数，例如十进制中的$10$，它的二进制是$1010$，三进制是$101$，所以10在二、三进制中是一个二阶交替数。 类似的，三阶、四阶交替数也可能存在。给出指定的进制范围、十进制数范围以及阶数目标，输出其中满足条件的多阶交替数。

输入格式

5个整数a,b,x,y,k。 [a,b]表示给定的进制范围 [x,y]表示查找的十进制数范围 k 是目标阶数 2 1 k=2,3,4

输出格式

一行一个满足要求的多阶交替数，以十进制形式输出

样例

输入

9 10 1 200 2

输出

191

样例解释

191的九进制是$232$，十进制是$191$，所以191属于[9,10]进制范围内的一个二阶交替数。

提示

交替数至少是三位数。