**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<10^{9}) , **m** (0<m<10^{9},m³n) and **k** (0<k<10^{9}) 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
**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 < 10^{9}) and **n** (n < 10^{9}) 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=11_{17}=18_{10}

The greatest exponents of two and three, such
that remainder of **a** divided by any of these
numbers is 0, are 2 (2^{1})
and 9 (3^{2})

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):

**+**+ + +

+ +

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