The table does not contain empty columns, i.e. each column contains at least one cell with non-empty text.

It is required to format a given table making its width (the length of table line) minimal.

Input data

Input data file INPUT.TXT contains an edited table. It consists of no more than 100 lines and line length is no more then 255 characters. Lines themselves do not contain leading and trailing spaces. The file does not contain empty lines.

An example of input data file:

Output data

Write to the output data file OUTPUT.TXT the aligned table. Output lines should not contain leading and trailing spaces. The output should not contain empty lines. The input data provides that the width of the formatted table does not exceed 255 characters.

Our example gives:

 

Problem B: Black Box

Input File	INPUT.TXT
Output File	OUTPUT.TXT
Time-limit/Test:	20 seconds

Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:

Let us examine a possible sequence of 11 transactions:

N	Transaction	i	Black Box contents after transaction (elements are arranged by non-descending)	Answer
1	ADD (3)	0	3
2	GET	1	3	3
3	ADD (1)	1	1, 3
4	GET	2	1, 3	3
5	ADD (-4)	2	-4, 1, 3
6	ADD (2)	2	-4, 1, 2, 3
7	ADD (8)	2	-4, 1, 2, 3, 8
8	ADD (-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD (2)	4	-1000, -4, 1, 2, 2, 3, 8

It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions - 30000 of each type.

Let us describe the sequence of transactions by two integer arrays:

1. A(1), A(2), ..., A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M<=30000 . For the Example 1 we have A=(3, 1, -4, 2, 8, -1000, 2).

2. u(1), u(2), ..., u(N) : a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example 1 we have u=(1, 2, 6, 6).

The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u (N) is sorted in non-descending order, N<=M and for each p (1<=p<=N) an inequality p<=u(p)<=M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p- minimum number from our A(1),A(2),...,A(u(p)) sequence.

Input data

Input data file INPUT.TXT contains (in given order): M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). All numbers are divided by spaces and (or) carriage return characters.

Input data file, corresponding to Example 1:

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

Output data

Write to the output data file OUTPUT.TXT Black Box answers sequence for a given sequence of transactions. The numbers can be separated with spaces and end-of-line characters.

Our example gives:

3
3
1
2

Output File	OUTPUT.TXT
Tools	Turing Machine interpreter TURING.EXE
Time-limit/Test:	15 seconds

The storage of Turing Machine consists of unlimited (to both sides) tape M. Each cell of M can store one of the three characters "0", "1" or "E". Its read/write head moves along the tape M. At each moment the head is able to observe one character of the tape (the current character). The machine is also equiped with a tape OUT to output the result. Allowed characters on the output tape are "0" and "1". The machine always writes to the OUT in a strict sequence from left to right. At each moment the machine is in one of N states.

Turing Machine operates in the single-stepping regime. Its program is a set of rules which defines an action depending on a current character value and the machine's state. During one action (step) the machine can execute any combination of the following operations:

turn to a new state;
alter the current cell value (value of the cell of the tape M pointed by the head);
move the head by 1 cell leftward or rightward;
write one character to the output tape OUT.

The states are numbered by integers from 1 to N. The Machine starts working the an initial state S. It stops when the current state and the current character matches no rule.

The program for Turing Machine is located in a text file as follows. The first line contains the number of states N, the second - the initial state S. The remainder of the file is the list of rules. Each rule is located in a single line in the following format:

where

q and w:	the current state and the current character;
q1 and w1:	the new state and the character to be written to the current cell (q1 can be equal to q, and in this case there is no turning to a new state; similarly, the value of the current cell does not alter when w1 equals w);
d:	a number -1, 0 or 1, setting the head movement (-1 - to the left, 0 - do not move, 1 - to the right);
e:	the character to be written to the output tape OUT (no writing is performed if e absents)

The machine should be simple, i.e. there should be no different rules with the same values of q and w. The rules enumeration order is arbitrary. The of q, w, q1, w1, d and e values are separated with spaces. The file can include empty lines and comments. The comment starts with ";" character and follows up to the end of line.

An input data for Turing Machine is a string of characters "0", "1" and "E". These characters are being written in adjacent cells of tape M and the head is set at the first character position. Character "E" is being written to all other cells of unlimited tape M. As a result, the machine works out a string of "0" and "1" characters, formed on the output tape OUT when the machine stops.

An example below contains a program turning an input sequence of "0" and "1" to the reverse order.

3
1
2 E 3 E 0
1 1 1 1 1
2 0 2 0 -1 0
2 1 2 1 -1 1   ; A comment
1 0 1 0 1
1 E 2 E -1

Write a program for Turing Machine which solves the task Q.

Task Q:

Tape M contains a positive integer X. It is required to write to the output tape the square of this number, i.e. C*C. Values C and C*C are presented in binary notation. In the initial state the head points at the last left digit of the number. Character "E" is written to all other cells of unlimited tape M. The input number does not include leading zeroes. The output also should not include leading zeroes. For example, if we had "1011" on tape M, the output should be "1111001". The program should meet the following restrictions: 1) the number of states N<=1000; 2) the number of operations is no more than 100+100*K*K steps, where K is a number of input binary number digits; 3) the absolute head move (a number of cells having been observed by the head) is no more than 10+10*K.

Output data

Your program for Turing Machine solving the task should be written to the output data file OUTPUT.TXT.

Tools

There is an interpreter of Turing Machine at your disposal. To call the interpreter, type

TURING <Program file name> [<File name with the input string>]

from DOS command prompt. If the second parameter is not set, the input string is read from the keyboard. The interpreter has a built-in debugger which allows you to execute a program by steps. Follow the instructions of the interpreter prompt.

Examples:

TURING example.t input.txt
TURING solution.t

Testing notes

Do not forget that the solution for the task C is a usual program on one of allowed programming languages. Your program should create output data file OUTPUT.TXT containing Turing Machine's program to solve task Q. Testing results Compilation error, Time limit exceeded, Runtime error concern the usual program while Presentation error and Wrong answer concern the Turing Machine's program from OUTPUT.TXT. Presentation error is reported in the following cases:

No output data file OUTPUT.TXT
The number of states N > 1000
Error in your program for Turing Machine

Correct (from the point of view of syntax) Turing Machine's program is being checked on the certain set of tests. If the answer is not correct or the program exceeds imposed restrictions to the number of operations or the absolute head move, you are reported Wrong answer. The task C requires no input data, that is why the reported wrong test number is always 1.

We would recommend to check your solutions with the given interpreter.

 

Problem D: DEL command

Input File	INPUT.TXT
Output File	OUTPUT.TXT
Time-limit/Test:	15 seconds

It is required to find out whether it is possible to delete given files from MS-DOS directory executing the DEL command of MS-DOS operation system only once. There are no nested subdirectories.

A note

DEL command has the following format: DEL wildcard

The actual wildcard as well as a full file name can be made up either of a name containing 1 up to 8 characters or of a name and extension, containing up to 3 characters. The point character "." separates the extension from the file name. The extension can be empty and this is equivalent to a name without any extension (in this case a wildcard ends with a point). In a wildcard the characters "?" and "*" can be used. A question mark substitutes exactly one character of the full file name excluding a point, an asterisk - any sequence of characters (containing no points) even empty one. An asterisk can appear only at the last position of the name and the extension.

MS-DOS system can permit maybe other wildcards but they can not be used in this task. File names and extensions consist only of Latin capitals and digits.

Input data

Input data file INPUT.TXT contains a list of full file names without empty lines and spaces. Each name is written in a separate line of input data file and preceded with a control sign: "-" for delete or "+" for keep. Full file names are not repeated. The list comprises at least one file, and at least one file is marked to be deleted. There are no more than 1000 files.

Output data

Write to the first line of output data file OUTPUT.TXT the required DEL command (only one proposal) or IMPOSSIBLE if there is no solution. A space should separate "DEL" from wildcard.

Input data file example:

-BP.EXE
-BPC.EXE
+TURBO.EXE

Possible output data file for our example:

DEL ?P*.*

Input File	INPUT.TXT
Output File	OUTPUT.TXT
Time-limit/Test:	15 seconds

Two points A (x1, y1, z1) and B (x2, y2, z2) are placed on the surface of parallelepiped P = {(x, y, z): 0<=x<=L, 0<=y<=W, 0<=z<=H} with L*W*H dimensions (see figure). These two points can be linked with various curves lying on the surface of P. You are to find out the square of the shortest curve length.

Parallelepiped dimensions L, W, H and coordinates of the points are integers, 0<=L,W,H<=1000.

Input data

Input data file INPUT.TXT contains (in indicated order): L, W, H, x1, y1, z1, x2, y2, z2. The numbers are separated with spaces and end-of-line characters.

Output data

Output data file OUTPUT.TXT should contain the square of the shortest curve length between points A and B on the surface of P.

Input data file example:

5 5 2
3 1 2
3 5 0

Output data file for our example:

36

Input File	INPUT.TXT
Output File	OUTPUT.TXT
Time-limit/Test:	20 seconds

From task B (Black Box): The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u (N) is sorted in non-descending order, N<=M and for each p (1<=p<=N) an inequality p<=u(p)<=M is valid.

Making tests for task B we have met with the following problem. For setting a random sequence {u(i)} a usual random data generator did not fit. As the sequence itself had been imposed certain restrictions, the method of choosing the next random element (in the interval defined by restrictions) did not give the random sequence as a whole.

We have come to a conclusion that the problem can be solved in the following way. If we arrange all possible sequences in certain order (for example, in lexicographical order) and assign each sequence its number, after choice of the random number it is possible to take the correspondent sequence for the random one. At the first glance it seems enough to make up a program generating all these sequences in such order. Alas! Even having not great values of M and N it would have taken any powerful modern computer centuries to enumerate all such sequences. It turned out it was possible to avoid generating all sequences if we managed to create required sequence according to its number immediately. But even this statement does not cover all. As the amount of sequences is quite large, the number can be a long one, composed of hundreds decimal digits, though our random data generator could give only normal numbers. We decided to produce a long random number from a real random number distributed in [0,1]. Namely, present the number in binary notation: 0.b(1)b(2)..., where all b(i) = 0 or 1. Let us set a regulation to associate such real number to an integer from [A,B] segment:

Formula 1:

Here we suppose, that A<=B, p>=0, and "div 2" is an integer division by 2.

Let M, N (1<=N<=M<=200) and a binary real number 0.b(1)b(2)...b(p) (1<=p<=400) be given. Write a program to find out the corresponding u(1), u(2), ..., u(N) sequence, i.e. to find a sequence with G(1, T, 0.b(1)b(2)...b(p)) number in lexicographical order of all possible {u(i)} for the given M and N (T - the quantity of such sequences). Numeration begins with 1. Keep in mind that in lexicographical order {l(i)} proceeds {h(i)} if after omitting equal beginnings, the first number of {l(i)} tail is smaller than the first number or {h(i)} tail. Example 1 illustrates the list of all possible sequences for M = 4 and N = 3 in lexicographical order.

Example 1:

   1, 2, 3
   1, 2, 4
   1, 3, 3
   1, 3, 4
   1, 4, 4
   2, 2, 3
   2, 2, 4
   2, 3, 3
   2, 3, 4
   2, 4, 4
   3, 3, 3
   3, 3, 4
   3, 4, 4
   4, 4, 4

Input data

The first line of input data file INPUT.TXT contains M and N. The second line contains binary real number 0.b(1)b(2)...b(p) (without leading, trailing and other spaces).

Input data file example:

4 3
0.01101101011110010001101010001011010

Output data

Write into the output data file OUTPUT.TXT the corresponding sequence u(1), u(2), ..., u(N). The sequence numbers should be separated with spaces and end-of-line characters.

Our example gives:

2
2
4

A note (it does not concern the solution of this task):

The choice of random binary vector 0.b(1)b(2)...b(p) does not give an absolute uniform random data generator if we use Formula 1. However, taking into account the fact that [A,B] interval is big we shall obtain a distribution applicable in most cases.

 

Problem G: Moscow time

Input File	INPUT.TXT
Output File	OUTPUT.TXT
Time-limit/Test:	15 seconds

In e-mail the following format for date and time setting is used:

Here EDATE is the name of date and time format, the text to the right from "::=" defines how date and time are written in this format. Below the descriptions of EDATE fields are presented:

Day_of_week	The name of a day of the week. Possible values: MON, TUE, WED, THU, FRI, SAT, SUN.The name is followed by "," character (a comma).
Day_of_month	A day of the month. Set by two decimal digits.
Month	The name of the month. Possible values: JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,SEP, OCT, NOV, DEC.
Year	Set by two or four decimal digits. If a year is set by two decimals it is assumed that this is anumber of the year of the XX century. For instance, 74 and 1974 set a year of 1974.
Time	Local time in fomat hours:minutes:seconds, where hours, minutes and seconds are madeup of two decimal digits. The time keeps within the limits from 00:00:00 to 23:59:59.
Time_zone	Offset of local time from Greenwich mean time. It is set by the difference sign "+" or "-"and by sequence of four digits. First two digits set the hours and the last two - minutes ofoffset value. The absolute value of the difference does not exceed 24 hours. Time zone canalso be presented by one of the following names: Name Digital value UT -0000 GMT -0000 EDT -0400 CDT -0500 MDT -0600 PDT -0700

Each two adjacent fields of EDATA are separated with exactly one space. Names of day of the week, month and time zone are written in capitals. For instance, 10 a.m. of the Contest day in St.Petersburg can be presented as

Write a program which transforms the given date and time in EDATE format to the corresponding date and time in Moscow time zone. So called "summer time" is not taken into consideration. Your program should rely on the predefined correctness of the given Day_of_week and Time_zone.

A note

	Moscow time is 3 hours later than Greenwich mean time (time zone +0300)
	Months: January, March, May, July, August, October and December have 31 days. Months: April, June, September and November have 30 days. February, as a rule, has 28 days, save for the case of the leap year (29 days).
	A year is a leap year if valid one out of two following conditions: Á) its number is divisible by 4 and is not divisible by 100; Â) its number is divisible by 400.

For instance, 1996 and 2000 are the leap years, while 1900 and 1997 are not.

Input data

Input data file INPUT.TXT contains date and time in EDATE format in the first line. Minimum permissible year in the input data is 0001, maximum - 9998. Input EDATA string does not contain leading and trailing spaces.

Input data file example 1:

SUN, 03 DEC 1996 09:10:35 GMT

Input data file example 2:

WED, 28 FEB 35 23:59:00 +0259

Output data

Output data file OUTPUT.TXT must contain a single line with date and time of Moscow time zone in EDATE format. In output EDATE string a Year can be presented in any of the two allowed ways. The output string should not include leading and trailing spaces.

Possible output for Example 1:

SUN, 03 DEC 1996 12:10:35 +0300

Possible output for Example 2:

THU, 01 MAR 1935 00:00:00 +0300