# Elimination round completed

"A" Small Numbers
Time limit 2 seconds 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 t — the number of test cases (1 ≤ t ≤ 500).

Each test case is described by a single line containing integers a and b (1 ≤ a, b ≤ 109) — Vlad's favorite numbers.

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
```
"B" New Keyboard
Time limit 2 seconds 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 n, a, b and c — the number of layouts, the number of milliseconds, to switch the layout without a previous switch, to switch the layout after a switch, and to type a character, respectively (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 109, 1 ≤ c ≤ 109).

The following n lines describe the layouts. Each layout is described by a string that contains all lowercase characters of the English alphabet that can be typed using this layout. Each character is specified at most once for each layout. Characters in each string are ordered alphabetically.

The last line contains a string s — the message that the Petya wants to type (length of s is from 1 to 2 000, inclusive). The string s consists of lowercase English letters.

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
```
"C" Folding the Figure
Time limit 2 seconds 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 t (1 ≤ t ≤ 200).

Each of the t test cases is described in the following way: the first line of the description contains two integers n, k — the number of painted squares in the folded figure and the number of painted squares in the original figure (1 ≤ n < k ≤ 105).

Each of the following n lines contains two integers xi, yi — coordinates of the i-th painted square's bottom left corner ( - 108 ≤ xi, yi ≤ 108). It is guaranteed that all painted cells are distinct and form a connected figure.

It is guaranteed that the sum of values of k in all test cases of one input data doesn't exceed 105.

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 k lines must contain two integers (x'i, y'i) each — the coordinates of the squares of the connected figure that can be folded along the given line to get the figure from the input data.

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 x'i, y'i, and the coordinate of the folding line must not exceed 109 by their absolute values. It is guaranteed that the required figure exists. If there are several possible answers, output any of them.

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```
"D" Acute Triangles
Time limit 4 seconds 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 t — the number of test cases (1 ≤ t ≤ 666).

Each test case is described by a line containing integer n (3 ≤ n ≤ 2000) — the number of points.

The following n lines contain two integers xi, yi each ( - 109 ≤ x, y ≤ 109) — coordinates of the points. It is guaranteed that in one test case all points are distinct.

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
```
"E" Joining Arrays
Time limit 4 seconds 256 megabytes

Consider two arrays of integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bm]. 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 = [r1, r2, ..., rk], that there are two non-empty sequences of indices 1 ≤ i1, 1 < i1, 2 < ... < i1, t ≤ n and 1 < j1, 1 < j1, 2 < ... < j1, k - t ≤ m in the original arrays, and two sequences of indices 1 ≤ i2, 1 < i2, 2 < ... < i2, t ≤ k and 1 ≤ j2, 1 < j2, 1 < ... < j2, k - t ≤ k, such that:

• For each 1 ≤ p ≤ t, 1 ≤ q ≤ k - t we have i2, p ≠ j2, q;
• For each 1 ≤ p ≤ t we have ai1, p = ri1, p;
• For each 1 ≤ p ≤ k - t we have bj1, p = rj1, 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 n — length of array A (1 ≤ n ≤ 3000).

The second line contains n integers ai — array A (1 ≤ ai ≤ 3000).

The third line contains m — length of array B (1 ≤ m ≤ 3000).

The fourth line contains m integers bi — array B (1 ≤ bi ≤ 3000).

The last line contains integer k (2 ≤ k ≤ n + m).

Output format

Output k-join of the given arrays.

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
```
"F" Two Trees
Time limit 4 seconds 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 t — the number of tests (1 ≤ t ≤ 104).

Each of the following t test is described in the following way: the first line contains one integer n — the number of vertices (2 ≤ n ≤ 105).

The following n lines describe vertices, the i-th of them first contains an integer cnti — the number of vertices of the vertex i, followed by cnti integers — numbers of the children of the i-th vertex, in order. Vertices are numbered starting from 1. The root of the tree is the vertex number 1. It is guaranteed that the graph is the correct tree rooted at 1.

The sum of values of n for all tests in one input data doesn't exceed 2·105.

Output format

For each test case output maximal k such that there are two equal k-subtrees with different roots.

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
```

### Send solution

Maximal size is 256kb 