- Final
**Elimination**- Third qual
- Second qual
- First qual
- Warm-up

# Elimination round completed

## Tasks

Show one task per page / all tasks on one page

Time limit | 2 seconds |
---|---|

Memory limit | 256 megabytes |

Little Vlad has two favorite numbers *a* and *b*. Recently, he was taught in school the division and multiplication operations and he immediately started dividing and multiplying his favorite numbers.

He wrote *a* and *b* in his notebook and came up with three cool operations which he wants to perform on his numbers:

- Divide both numbers by one of their common divisors;
- Divide
*a*by one of his divisor*g*, multiply*b*by*g*; - Divide
*b*by one of his divisor*g*, multiply*a*by*g*.

After performing every operation he erases his old numbers, replacing them with new ones. He may choose to continue performing operations or to stop.

Since Vlad is small, he wants numbers to be smaller. Thus, he is trying to minimize sum of *a* and *b*, but can't handle it on his own. Help him to determine minimum sum that he can obtain by performing these operations and give an example of final *a* and *b* with such sum.

Input format |
Input data contains multiple test cases. The first line of input contains integer Each test case is described by a single line containing integers |
---|---|

Output format |
For each test case output one line — the pair with the minimum sum that can be obtained by performing operations from the list. |

Examples |
Input data
2 4 5 4 6
Output data
1 5 2 3 |

Time limit | 2 seconds |
---|---|

Memory limit | 256 megabytes |

Petya has bought a new keyboard. It supports *n* layouts, each layout allows to input some subset of characters of the lowercase English alphabet. Layouts are enumerated from 1 to *n*.

Petya wants to type some message now, it consists of *m* lowercase letters of the English alphabet. Initially the first layout is active. Petya can do one of the following two actions:

- Switch layout to the next one. If the current layout is
*i*, the new layout will have number*i*mod*n*+ 1, where mod denotes the remainder of the division. If the previous action was also layout switch, this action takes*b*milliseconds, in the other case it takes*a*milliseconds. - Type a character. Petya can add the typed character to the end of the current message. He spends
*c*milliseconds for this action.

Help Petya to find out what minimal time he needs to type the message, or detect that it is impossible to type the message using his new keyboard. The final layout of the keyboard doesn't matter.

Input format |
The first line of the input data contains four integers The following The last line contains a string |
---|---|

Output format |
Output one integer — the minimum number of milliseconds needed to type the message. Output - 1 if it is impossible to type the message. |

Examples |
Input data
5 3 2 1 abc d e f def abcdef
Output data
15 |

Input data
1 1 1 1 a z
Output data
-1 |

Time limit | 2 seconds |
---|---|

Memory limit | 256 megabytes |

Petya was getting bored at his Math lesson, so he started painting squares at his grid paper. When he got bored of that action as well, he noticed that he now has a connected set of *k* painted squares — it is possible to get from any painted square to any other painted one by moving between painted squares sharing a common side.

He cut the figure away from the sheet of paper and folded it along some grid line (horizontal or vertical, he didn't remember). After that he painted squares of some other grid paper to create the copy of the folded figure. Now Petya has lost his original figure, so all he has is the copy of it after folding. Now Petya wants to restore the figure.

It is difficult to restore the figure exactly, but Petya has decided that he would like to have at least some figure of *k* squares that can be folded to get the same folded image. Help him, find some connected figure of *k* squares that can be folded the required way.

Consider for example the second sample test. It has a folded figure that is similar to an upside-down "U" letter, the original figure contains 12 squares. One way the original figure could look like is shown at the picture, it was folded along a line *y* = 3:

Input format |
Input data contains multiple test cases. The first line contains the number of test cases Each of the Each of the following It is guaranteed that the sum of values of |
---|---|

Output format |
For each test case output the answer to this test. Output the description of the figure and the way to fold it to get the input figure. The first line must contain the description of the folding line. The following The folding line description must be one of the following 4: - L
*num*— fold along the line*x*=*num*, put left side atop the right one; - R
*num*— fold along the line*x*=*num*, put the right side atop the left one; - U
*num*— fold along the line*y*=*num*, put the top side atop the bottom one; - D
*num*— fold along the line*y*=*num*, put the bottom side atop the top on.
All |

Examples |
Input data
2 7 14 0 0 0 1 0 2 1 2 2 2 2 1 2 0 7 12 0 0 0 1 0 2 1 2 2 2 2 1 2 0
Output data
L 0 0 0 0 1 0 2 1 2 2 0 2 1 2 2 -1 0 -1 1 -1 2 -2 2 -3 2 -3 1 -3 0 U 3 0 0 0 1 0 2 1 2 2 2 2 1 2 0 0 3 1 3 2 3 0 4 2 4 |

Time limit | 4 seconds |
---|---|

Memory limit | 256 megabytes |

Recently Moscow high school student Dmitri Zakharov set a new record on the number of points in *d*-dimensional space, such that all triangles with vertices in those points are acute.

Tanya wants to compete with Dmitri. Of course she is planning to use the computer. To make a good start, she decided to solve the following problem. Given *n* points on a plane, find the number of acute triangles that have vertices in those points. The triangle is acute if all of its angles are less than 90 degrees.

Input format |
Input data contains multiple test cases. The first line of input contains integer Each test case is described by a line containing integer The following The total number of points in all test cases of one input data doesn't exceed 2000. |
---|---|

Output format |
For each test case output one line — the number of acute triangles with vertices in the given points. |

Examples |
Input data
2 5 1 1 2 2 3 3 4 1 6 4 5 0 0 3 1 5 1 5 -1 1 3
Output data
3 4 |

Time limit | 4 seconds |
---|---|

Memory limit | 256 megabytes |

Consider two arrays of integers *A* = [*a*_{1}, *a*_{2}, ..., *a*_{n}] and *B* = [*b*_{1}, *b*_{2}, ..., *b*_{m}]. Let us introduce their *k*-join as a lexicographically smallest array *R* of length *k*, that can be divided to two non-empty subsequences, first of which is a subsequence of *A*, and the second one is a subsequence of *B*.

Formally speaking, you need to find such array *R* = [*r*_{1}, *r*_{2}, ..., *r*_{k}], that there are two non-empty sequences of indices 1 ≤ *i*_{1, 1} < *i*_{1, 2} < ... < *i*_{1, t} ≤ *n* and 1 < *j*_{1, 1} < *j*_{1, 2} < ... < *j*_{1, k - t} ≤ *m* in the original arrays, and two sequences of indices 1 ≤ *i*_{2, 1} < *i*_{2, 2} < ... < *i*_{2, t} ≤ *k* and 1 ≤ *j*_{2, 1} < *j*_{2, 1} < ... < *j*_{2, k - t} ≤ *k*, such that:

- For each 1 ≤
*p*≤*t*, 1 ≤*q*≤*k*-*t*we have*i*_{2, p}≠*j*_{2, q}; - For each 1 ≤
*p*≤*t*we have*a*_{i1, p}=*r*_{i1, p}; - For each 1 ≤
*p*≤*k*-*t*we have*b*_{j1, p}=*r*_{j1, p}.

For example if *A* = [1, 2, 1, 3, 1, 2, 1], *B* = [1, 2, 3, 1], and *k* = 9, their *k*-join is the array *R* = [1, 1, 1, 1, 2, 1, 2, 3, 1] (subsequence from the first array — [1, 1, 1, 2, 1], subsequence from the second array — [1, 2, 3, 1]).

For two given arrays *A* and *B*, and an integer *k* find their *k*-join *R*.

Input format |
The first line of input contains The second line contains The third line contains The fourth line contains The last line contains integer |
---|---|

Output format |
Output |

Examples |
Input data
7 1 2 1 3 1 2 1 4 1 2 3 1 9
Output data
1 1 1 1 2 1 2 3 1 |

Time limit | 4 seconds |
---|---|

Memory limit | 256 megabytes |

Consider a rooted tree. Let us consider a vertex *v* that has at least one vertex in its subtree that has distance *k* from *v*. Let us call a tree that we get from a subtree rooted at *v* by removing all vertices that are at distance greater than *k* from *v* its k-subtree rooted at *v*. For example, the picture below shows 2-subtree of the vertex 3 in red.

Let us call two subtrees equal, if it is possible to renumber vertices of one of them to get the other one. You are not allowed to change the order of children of a vertex. For example, the following two trees are not equal:

You are given a rooted tree. Find the greatest *k* such that the given tree has two equal *k*-subtrees with different roots. These trees are allowed to have vertices in common.

The picture shows trees from sample test.

The first example has equal 1-subtrees rooted at 2 and 3.

The second example has equal 3-subtrees rooted at 1 and 4.

The third example has equal 0-subtrees rooted at 1 and 2.

Input format |
Input data contains multiple test cases. The first line contains Each of the following The following The sum of values of |
---|---|

Output format |
For each test case output maximal |

Examples |
Input data
3 5 2 2 3 1 4 1 5 0 0 8 1 2 2 3 4 0 1 5 2 6 7 0 1 8 0 2 1 2 0
Output data
1 3 0 |