PROBLEMS FROM THE 3RD STAGE OF THE 11TH LATVIAN OLYMPIAD IN INFORMATICS

1. Series

All the natural numbers from n to m (inclusively) are written in a row without separating symbols, thus creating a series of decimal digits.

For example, if n=98 and m=102, this series is 9899100101102.

Then all the digits are sorted in a non-increasing order - first the greatest digits, then the next greatest, etc.

For the example above this sorted series is 9998211110000.

For the values of natural numbers n,m and k given in the input your task is to compute, which digit will be in the k-th position of the sorted series.

Input data

The values of three natural numbers n (0<n<109) , m (0<m<109,m³n) and k (0<k<109) are input from the keyboard.

Output data

The digit at the k-th position of the sorted series must be output on the screen. If length of the series is less than k, a single word NAV must be output on the screen.

Examples

Input data            Output data

98 102 4  8

Input data                  Output data

9999 9999 5  NAV

2. Sevens, twos and zeros

The task is to write a program that outputs the smallest possible number s for an input natural number n. The number s must have the following properties:

• s³n;
• the value of s written in decimal form contains only digits 7, 2 and 0 and it does not start with 0;
• the decimal form of s contains at most 20 digits;
• the remainder of s divided by n equals 0.

Input data

A value of natural number n (0 < n < 500000) is input from the keyboard.

Output data

The number s as described above must be output on the screen. If it is not possible to find the corresponding value of s to the given value of n, output one word "NAV".

Examples

Input data  Output data

3 27

Input data  Output data

61   70272

3. Ones

The form of a natural number a in a number system with base p contains of n ones (digts "1") in a row.

Your task is to write a program that computes the greatest values of exponents of numbers 2 and 3 such that the remainder of a divided by both these values the remainder is 0.

Input data

Two values of natural numbers p (1 < p < 109) and n (n < 109) are input from the keyboard.

Output data

Two non-negative integer numbers must be output on the screen : the values of the greatest exponents of two and three.

Examples

Input data  Output data  Notes

17 2   1 2  a=1117=1810

The greatest exponents of two and three, such that remainder of a divided by any of these numbers is 0, are 2 (21) and 9 (32)

Input data  Output data

10 4  0 0

4. The magician

The circus magician Tālrīts Vakars shows magic tricks. In his demonstrations he uses only :

 baloons ( ), doves ( ), rabbits ( ) and poodels ( ).

Tālrīts can carry out only the following tricks: (baloons and animals in the direction shown by the arrow are converted to different animals):

1.  + +
2.  + +
1.  + +

Your task is to write a program that for the input number of baloons, doves, rabbits and poodels computes the maximum possible number of rabbits that Tālrīts can obtain and the least number of tricks required to do this.

Input data

The values of non-negative integer numbers b (number of baloons, b£150), d (number of doves, d£150),

t (number of rabbits, t£150) and p (number of poodels, p£150) are input from the keyboard. It is also known that b + d + t + p £ 250.

Output data

The maximum possible number of rabbits that Tālrīts can obtain must be displayed on the screen, as well as (separated by a space symbol) the minimal number of tricks that is required to obtain this number of rabbits.

Examples

Input data            Output data

9 17 1 3  10 3

Input data            Output data

3 0 2 2   4 2