THE 13TH LATVIAN OLYMPIAD IN INFORMATICS
1ST STAGE SUGGESTED PROBLEMS

1. Number

Write a program that for the input natural numbers n and m finds the smallest possible natural number k, for which both of the following properties simultaneously apply:

Input data
The first line of the text file SKAITLIS.DAT contains two natural numbers n (0 < n £ 32000) and m (0 < m £ 500), separated by a space symbol.

Output data
The value of the number k must be output to the only line of the file SKAITLIS.REZ.

Example
Input data (file SKAITLIS.DAT)
38 17

Output data (file SKAITLIS.REZ)
51



2. Circle

There are N small circles positioned in a large circle. There is a natural number written in each of the circles. Each of the numbers is in every move replaced using the following algorithm:

For each three numbers (the number in the current circle and each of the neighboring circles) three numbers are determined - the greatest, the smallest, and "the remaining one".

The value written in the new circle is equal to the greatest - the smallest+ the remaining one.

Thus, if the value written in the considered circle is 7, while the nearby numbers are 3 and 8, the greatest is 8, the smallest 3 and the remaining one is 7. In the next turn the number 12 is written in the circle (as 8-3+7=12).

One turn is shown in the picture below (note that the values in all the circles are changed simultaneously):

Your task is for the input numbers N and M, as well as the numbers positioned in the circle, to determine what numbers will be written in the circle after M moves.

Input data
The first line of the text file APLIS.DAT contains two natural numbers N (N £1000) and M (M £10), separated by a space symbol. In each of the following N lines there is given one number that is contained by the respective circle. The numbers are given in clockwise direction. The values do not exceed 100 in any of the small circles.

Output data
The text file APLIS.REZ must contain exactly n lines - one number per line. These must be the numbers to be written in the corrseponding small circles after M turns. The numbers must be output exactly in the same order as given in the input data (one after another in the clockwise direction, starting with the same circle the input data started with).

Example
Input data (file APLIS.DAT)     Output data (file APLIS.REZ)
7 2                  16
1                    9
2                    7
3                    8
4                    9
5                    13
6                    12
7



3. Password

In computer systems passwords are used to protect data from unauthorized access - these passwords are specific strings of symbols. However, it sometimes happens that the person knows the real password but mistypes it. The following typing errors are the most common:

1) a symbol is missing;
2) an extra symbox is inserted;
3) two symbols next to each other are swapped;
4) instead of one symbol another is entered. Thus, if the real password would be "SlePENs", the first error type would be in the string "SlePNs", second type "SlePiENs", third type "SelPENs",fourth type "SlEPENs".

The specialists of the firm "Suspicion" have determined that the presence of one of the above errors during the entering of the password does not present significant danger to the safety of the system and that these strings can too be accepted as correct.

Your task is to write a program that for an input real password and an input string determines, whether the string can be accepted.

Input data
The small and capital letters in the input data are different symbols.
The first line of the PAROLE.DAT text file contains the real password - a string containing only letters of the latin alphabet. The length of this string does not exceed 250 characters.
The second line of the file contains the string to be checked, containing only latin letters. The length of the string does not exceed 250 characters.

Output data
The first line of the text file PAROLE.REZ must contain the word NEDER if the input string is unacceptable (the number of errors exceeds 1), or the word DER if the string is acceptable (it either is equal to the password or it contains exactly one error as described above. If the string is acceptable, the second line of the file must contain either 0 (if the password is the same as the string) or the information about the error type in the form of a natural number 1 to 4 (according to the error list above).

Examples
Input data (file PAROLE.DAT)         Output data ( file PAROLE.REZ)
SlePENs                DER
SelPENs                3

Input data (file PAROLE.DAT)         Output data ( file PAROLE.REZ)
SlePENs                NEDER
SelPeNs

Input data (file PAROLE.DAT)         Output data ( file PAROLE.REZ)
SlePENs                NEDER
SPelENs



4. Numbers
 
In a valid example of addition of two numbers A+B=C all the letters x (if there were these) were changed to y and vice versa. It is given that neither x, nor y are equal to zero and that x is not equal to y. Therefore, instead of the number A the equation contains the number A*, instead of B - B*, C - C*. Write a program that for the given number A*, B*, and C* finds and outputs the numbers A, B, and C.

Input data
The first line of the text file CIPARI.DAT contains the number A*, the second line - B*, the third - C*. The numbers do not start with zero and the length of each of the numbers does not exceed 20.

Output data
The first line of the CIPARI.REZ text file must contain the digits x and y, separated by a space symbol. The second line of the file must contain the number A, the third - B, the fourth - number C.

If more than one solution is possible, you only need to output any one of them.

Examples
Input data (file CIPARI.DAT)                     Output data ( file CIPARI.REZ)
923456781                   1 9
2009                        123456789
923458710                   2001
                            123458790

Input data (file CIPARI.DAT)                     Output data ( file CIPARI.REZ)
4242                        4 2
2424                        2424
6666                        4242
                            6666

Input data (file CIPARI.DAT)                     Output data ( file CIPARI.REZ)
53                          8 9
17                          53
70                          17
                            70



5. Lift

A skyscraper has n stories. It also has a lift working using only two keys ( and ). Pressing the key the lift moves exactly a stories upwards, pressing the key - exactly b stories downwards. If a command ordering to move above the n-th floor or below the 1st floor is received, the lift does not move. The lift is on the k-th floor. How many times, at least, must the above buttons be pressed to move to the m-th floor ?

For the given natural numbers n,a,b,k,m the smallest number of times required to push the button must be input.

Input data
The first line of the text file LIFTS.DAT contains five natural numbers n,a,b,k,m (n £ 10000; a<n; b<n; k £ n; m £ n). There is a whitespace between each two numbers.

Output data
The first line of the LIFTS.REZ text file must contain one integer - the least number of times buttons must be pressed to move the lift to the m-th floor.

If it is not possible to move the lift to the m-th floor, only the word NEVAR must be output to the first line of the text file.

Examples
Input data (file LIFTS.DAT)          Output data (file LIFTS.REZ)
100 4 2 1 22          NEVAR

Input data (file LIFTS.DAT)          Output data (file LIFTS.REZ)
11 2 3 10 6           3

                                    Comment: A possible order of presses of the buttons is: 


Home