## Problem A. Ascending arrays ≡

 Input file: Standard input Time limit: 1 sec Output file: Standard output Memory limit: 256 Mb

### Statement

There are three strictly increasing arrays of integers A1, A2, A3 with lengths N1, N2, N3.

Your program must find the count of triples of the same numbers simultaneously occurring in each of these arrays.

### Input format

First line contains N1, N2, N3.

Second line contains A11, A12, ..., A1N1

Third line contains A21, A22, ..., A2N2

Fourth line contains A31, A32, ..., A3N3

### Output format

A single integer — count of triplets.

### Constraints

1 ≤ N1, N2, N3 ≤ 105

0 ≤ Ai j ≤ 109

### Sample tests

No. Standard input Standard output
1
5 4 3
2 3 4 5 7
1 2 3 4
2 3 4

3

2
5 4 3
2 3 4 5 7
1 2 4 7
1 3 5

0


## Problem B. Batteries ≡

 Author: A. Karabanov Time limit: 1 sec Input file: Standard input Memory limit: 64 Mb Output file: Standard output

### Statement

A team of geologists is about to return from an expedition, but already prepares for the next one. The expedition leader sent a list of required items by radio.

Timofey is responsible for battery supplies. He has batteries of two types: AA and AAA. The message that he received looks like "quantity type" (without space). For example, a string "123AA" means that geologists need 123 batteries of the AA type, while a string "6AAA" means that they need 6 batteries of the AAA type.

Finally Timofey can get to work. Unfortunately, exactly one character in the message contains an error. Help Timofey to determine the maximum number of batteries of each type that geologists may require.

### Input format

The only string in the input file is the string s. It's guaranteed that the string contains only characters from the following set: "0123456789A" (no quotes). It's guaranteed that the original radio message was valid (in particular, there was no leading zeros), and that exactly one character in it was changed.

### Output format

The output must contain two nonnegative integers separated by a space — the largest number of if batteries of types AA and AAA respectively, which geologists may need according to their message.

3 ≤ len(s) ≤ 5

### Explanation of the samples

In the first sample the error may be in the first character. Then the original message could look like "923AA". The error could be in the second or in the third character, but Timofey still need to prepare at least 923 AA batteries. It's also possible that one of "A" characters was replaced with "3", and the original message was "12AAA". Thus Timofey needs at least 12 AAA batteries.

In the second sample the message could only be about AA batteries, while in the third one it could only be about AAA batteries.

### Sample tests

No. Standard input Standard output
1
123AA
923 12
2
9AA
8 0
3
AAAA
0 9

## Problem C. Comparison of graph layouts ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Young programmer Vasya is engaged in N-dimensional graph layout. As a result of the work of his algorithm, each vertex is assigned coordinates in the N-dimensional space. However, he did not take into account that the accuracy may be lost when the results are saved in different formats. Now he must examine files to determine which of them contains which graph.

We are given two graphs — original one and one read from file. Due to conversion vertex coordinates of the second graph may be shifted, but no more than by a given ε. Vertex indexing may be changed as well.

It is required to compare given graphs and reconstruct correspondence between their vertices if possible.

### Input format

Input data contains integer N — dimension of the space, V — number of vertices and E — number of edges.

Following is a set of the N ⋅ V coordinates of vertices of the original graph and set of the E edges specified by index pairs. Vertices are indexed from zero.

Next the second graph is given in the same format.

The ε precision is the last item of the input.

### Output format

Output data must contain V integers Li — index of the second graph vertex corresponding to i-th vertex of the original graph.

If it is not possible to restore correspondences, the output a single number  − 1.

### Constraints

Distance between any pair of vertices of the original graph is no less than 10 ⋅ ε, and all coordinates are in the range from  − 10 to 10.

1 ≤ N ≤ 5, 1 ≤ V ≤ 2 ⋅ 104, 0 ≤ E ≤ 2 ⋅ V,

10 − 6 ≤ ε ≤ 1

### Sample tests

No. Standard input Standard output
1
3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
4.20000  3.65000 -4.23000
1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
4.20300  3.65001 -4.23079

0 3
2 0
3 1
2 3
1 2

0.1

2
0
3
1

2
3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
4.20000  3.65000 -4.23000
1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
4.20300  3.65001 -4.23079

0 3
2 0
3 1
0 1
1 2

0.1

-1


## Problem D. Decision tree for matching ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Let we have set of the N strings of the same length are consisted by 0 and 1. Next some previously unknown string from this set will be selected, whose index need to guess.

It is required to define optimal in the worst case sequence of compares that allows to recognize index of the input string. Result need presented as decision tree.

Each non leaf node of this tree contains i — position number in which comparison need to perform. It has exactly 2 childs (for each character of the alphabet).

If in the i-th position of the string there is a character with the number k, transition to the appropriate subtree where the search will be continued is performed.

Leafs of this tree correspond to terminal states of search and contain indices of recognized strings.

### Input format

Input data contains N, followed by exactly N strings of the original set.

### Output format

Output data must contain decision tree written in the next format.

Leaf node starts from symbol '=', followed by string number
(indices of strings starting by zero).

Non-leaf node starts from '>',
followed by position number in which comparison will be performed.
(position starting by zero).

Next the according subtree is written in same way.

### Constraints

It is guaranteed that all strings of the original set are distinct.
Their length does not exceed 32.

2 ≤ N ≤ 16

### Sample tests

No. Standard input Standard output
1
5
0010111000
0111101101
0110110001
0011100101
0010111101

> 9
= 0
> 6
> 7
= 2
= 3
> 5
= 1
= 4

2
3
000
111
110

> 2
> 1
= 0
= 2
= 1


## Problem E. Equidistant shell ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

The equidistant shell of a three-dimensional body is the set of points external to it, within a distance of no more than a given δ. Example of equidistant shell of cube with its cross section is presented on picture.

Given an arbitrary convex polyhedron and a value of δ. You program must calculate volume of the equidistant shell.

### Input format

Input data contains original polyhedron presented in a following format.

First there is the integer V, followed by exactly 3 ⋅ V real numbers that are coordinates of the vertices.

Next, integer E, followed by exactly 2 ⋅ E numbers of the vertices, defining the edges pairwise.

Next is the integer F, followed by exactly F faces represented in the following format.

First integer number of edges N, followed by N indices of edges of this face in an arbitrary order.

Indices of the all elements start from zero.

The floating point value of δ is written at the end of the input data.

### Output format

Output data must contain the volume with an accuracy of at least 5 digits after decimal point.

### Constraints

All faces are non-degenerate and convex.

Vertex coordinates are in the range from  − 10 to 10.

Count of elements of each kind does not exceed 100.

0 ≤ δ ≤ 1

### Sample tests

No. Standard input Standard output
1
8
-1.00000 -1.00000 -1.00000
1.00000 -1.00000 -1.00000
-1.00000  1.00000 -1.00000
1.00000  1.00000 -1.00000
-1.00000 -1.00000  1.00000
1.00000 -1.00000  1.00000
-1.00000  1.00000  1.00000
1.00000  1.00000  1.00000

12
1 0
2 0
4 0
3 1
5 1
3 2
6 2
7 3
5 4
6 4
7 5
7 6

6
4 3 5 1 0
4 4 8 2 0
4 6 9 2 1
4 7 4 10 3
4 7 11 6 5
4 10 11 9 8

0.25

7.24355

## Problem F. Four-dimensional polytope ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Consider some convex four-dimensional polytope that presented by a mesh composed of such elements as vertices, edges, faces and three-dimensional bodies.

Each vertex is represented by four coordinates (x, y, z, w). Each edge is a straight line segment and is represented by a pair of vertices connected by it. Each face is a convex polygon and is represented by a set of its edges. Each body is a convex polyhedron and is represented by a set of its faces.

The polytope itself is specified by set of three-dimensional bodies bounding it.

You program must calculate volume of a cross-section of the polytope by 3D sub-space with w = 0.

### Input format

Input data contains sequence of the mesh elements.

First there is the integer V, followed by exactly 4 ⋅ V real numbers that are coordinates of the vertices.

Next, integer E, followed by exactly 2 ⋅ E numbers of the vertices, defining the edges pairwise.

Next is the integer F, followed by exactly F faces represented in the following format.

First integer number of edges N, followed by N indices of edges of this face.

The bodies specified by set of their faces are written in the same way.

Indices of the all elements start from zero.

### Output format

Output data must contain the volume with an accuracy of at least 5 digits after decimal point.

### Constraints

It is guaranteed that all mesh elements are non-degenerate.

Vertex coordinates are in the range from  − 10 to 10.

Count of elements of each kind does not exceed 1000.

### Sample tests

No. Standard input Standard output
1
5
-1.00000 -1.00000 -1.00000 -0.50000
0.00000  1.00000 -1.00000 -0.50000
1.00000  0.00000 -1.00000 -0.50000
0.00000  0.00000  1.00000 -0.50000
0.00000  0.00000  0.00000  0.50000

10
0 1
0 2
0 3
1 2
1 3
2 3
0 4
1 4
2 4
3 4

10
3 0 1 3
3 1 2 5
3 0 2 4
3 3 4 5
3 0 6 7
3 1 6 8
3 2 6 9
3 3 7 8
3 4 7 9
3 5 8 9

5
4 0 1 2 3
4 0 4 5 7
4 1 5 6 9
4 2 4 6 8
4 3 7 8 9

0.12500

## Problem G. Greedy replacement ≡

 Author: M. Sporyshev Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

Let we have array of integers ai. You can select in it no more than one number and replace it to other. Cost of this replacement is absolute difference new and old numbers.

It is required to find replacement with a minimum cost, so that a pair of same elements appears in the array of prefix sums of this array.

### Input format

First line of input data contains single number N — length of the array.

Second line contains the N integers ai.

### Output format

Output data must contains two integer numbers — index of element for replacement (starting by zero) and signed difference between new and old its values.

If there are many solutions, than output any from them.

2 < N < 100000

|ai| ≤ 109

### Sample tests

No. Standard input Standard output
1
2
1 1

1 -1

2
3
1 2 -3
2 1


## Problem H. Hamming sphere ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Four strings of the same length are composed of four characters ('A', 'B', 'C' and 'D').

Your program must find such a string that Hamming distance from it to any strings of original set is the same.

Moreover, such string must have the same length as the original strings.

If there are many answers, select any string that gives the minimum of distance.

### Input format

Input data contains four original strings.

### Output format

Output data must contain answer or empty string, if answer does not exist.

### Constraints

Length of original strings is from 1 to 32.

### Sample tests

No. Standard input Standard output
1
ABCDABCD
AABBAABB
AACCABCD
ABCDCCDD

AABDCACD

2
AAA
CBC
BCD
DDB


## Problem I. Inner triangles ≡

 Author: A. Karabanov Time limit: 1 sec Input file: Standard input Memory limit: 64 Mb Output file: Standard output

### Statement

Timofey was sitting on a math test. His test was completed, he even solved the test of his neighbour, beautiful Alena. Timofey was bored, so he started to draw on checkered sheet of paper.

At first, he drew a square with lines, parallel to sheet sides, and marked all vertices of this square. Then he marked additional a points on the first side of square, b additional points on second side of the square, c additional points on the third side and d aaditional points on the last side. Now he is interested, how many different nondegenerate triangles with vertices in marked points are there?

### Input format

The only line of input contains four space-separated natural numbers: a, b, c ї d.

### Output format

Print one integer — number of different nondegenerate triangles with vertices in marked points.

### Constraints

0 ≤ a + b + c + d ≤ 1000

### Sample tests

No. Standard input Standard output
1
1 0 0 0
9
2
1 2 3 4
329

## Problem J. Jumps of grasshopper ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Grasshopper moves along number line by jumps of integer length. It can jump both to positive and negative directions. Length of each jump can't equal zero.

It is required to calculate count of all different ways that grasshopper can get from point A to point B making at most N jumps,
whose total length shouldn't exceed some given L.

Since obtained count may be very great, remainder of its division by 109 expected as answer.

### Input format

Input data contains four integer numbers A, B, N и L.

### Output format

Output data must contain obtained number.

### Constraints

0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60

### Sample tests

No. Standard input Standard output
1
0 10 20 40
35498634
2
1 1 2 2
3

## Problem K. Kit of gauge blocks ≡

 Author: A. Karabanov Time limit: 1 sec Input file: Standard input Memory limit: 64 Mb Output file: Standard output

### Statement

When Timofey was cleaning garage of his grandfather, he found a strange box under the workbench. There were ceramic plates of different lengths. His father explained to him that it was a measuring device that allowed you to store and transmit a length. The plates are simply placed against each other (their surfaces are polished to such an extent that they hold on to each other without breaking up) until the desired length is reached. Unfortunately, many plates were lost, so now it's possible to have only a limited set of lengths. Timofey wants to find out what is the longest range of consecutive natural numbers that can be obtained from the remaining plates.

### Input format

The first line contains one integer n — the number of available plates. The second line contains n natural numbers xi — space-separated lengths of plates, sorted in non-descending order.

### Output format

Print one natural number — length of longest range of consecutive natural numbers that can be obtained from the remaining plates.

1 ≤ n ≤ 100

1 ≤ xi ≤ 1000

### Explanation of the sample

In the example you are given five plates with lengths 1, 4, 5, 7 and 15. It's possible to obtain lengths [1], [4 .. 13], [15 .. 17], [19 .. 28], [31 .. 32] ([a .. b] means, that it's possible to obtain any length from a to b inclusive). The longest range has length equal to 10, for example range [4 .. 13] or [19 .. 28].

### Sample tests

No. Standard input Standard output
1
5
1 4 5 7 15
10

## Problem L. LCA queries ≡

 Author: A. Usmanov Time limit: 1 sec Input / output: interactive Memory limit: 256 Mb

### Statement

This is an interactive problem. You will interact with a server by sending and receiving particular messages.

You are given a complete binary tree of height N having maximum possible number of nodes.

Nodes are numbered from 1 to 2N − 1.

Your task is to determine the number of root. You can perform requests to find least common ancestor (LCA) of any two nodes to achieve this. You are allowed to perform no more than N requests.

### Input format

The first line contains one integer N — height of the tree.

### Interaction protocol

To make a request print a line "? X Y", where X and Y — are integer numbers of nodes. After such a request you receive one integer — the number of least common ancestor of these two nodes.

When your program determines the root of the given tree, it should print "! X" and immediately stop.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

 Language C++ Pascal Java Python Code cout.flush() flush(output) System.out.flush() stdout.flush()

1 ≤ N ≤ 10

1 ≤ X, Y < 2N

### Explanation of the samples

The first sample contains the next tree:

### Sample tests

No. Standard input Standard output
1
3

2

5

7


? 3 6

? 1 5

? 2 4

! 7

2
1


! 1


1.796s 0.011s 45