Number#2418

Number

1 second
64 megabytes
Very easy

In some institutions, documents are numbered in an unusual way. One set of digits is used for odd positions, and generally, a different set for even positions (positions are counted from right to left starting from ). In different years, different sets of digits may be used. The only rule that is strictly followed is that within the given constraints, numbers are not skipped and maintain ascending order.

For example, if the digits , , are used in odd positions and , in even positions, the first few numbers are: , , , , , , , , , , , , , ...

You need to write a program that, given the digit sets for odd and even positions and a known sequential number of the document counted from , determines the number assigned to that document in the organization.

Input

The first line contains three integers , , . is the requested official number, and and are the number of digits used in odd and even positions, respectively. The second line contains the digits used in odd positions separated by spaces. The third line contains the digits used in even positions separated by spaces.

1 \leq N \leq 10^{55}, 2 \leq K, L \leq 10.

Output

The output file should contain a single line with the answer to the problem.

Examples

Example 1

Loading
Loading