Problem A. Arithmetic pairs ≡

Statement

Your program must calculate total number of such pairs of integers (p, n) that p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Input file format

Input file contains two integers A and B.

Output file format

Output file must contain a single integer — number of pairs.

Constraints

2 ≤ A ≤ B < 2⁶³

Sample tests

10 100

13

37 48

0

Problem B. Broken chessboard ≡

Statement

You are given a board of n × m cells, one of them is occupied by a chess knight. Some cells were removed from the board.

Your program must determine the minimal number of moves that a knight must perform to visit all cells of a given list in order, not visiting removed cells in the process.

On other words, given list of cells must be a subsequence of cells visited by the knight.

Input file format

Input file contains integers n and m — board size.

Next there is an integer P, followed by P pairs of integers (a_i, b_i) — coordinated of removed cells.

Next there is an integer L, followed by L pairs of integers (x_i, y_i) — coordinates of cells to visit (starting with initial position of the knight).

Output file format

Output file must contain a single integer — minimal number of moves.

If there is no solution, output −1.

Constraints

0 < |x_i+1 − x_i| + |y_i+1 − y_i|, 2 ≤ (n, m) ≤ 100,

0 ≤ (a_i, x_i) < n, 0 ≤ (b_i, y_i) < m,

0 ≤ P ≤ 5000, 2 ≤ L ≤ 100

Sample tests

5 5

4
2 3
4 3
2 4
1 1

3
3 1
1 2
0 3

5

5 5

4
2 2
4 3
2 4
1 1

3
3 1
2 3
0 3

-1

Problem C. Cut the band ≡

Statement

Young programmer Vasya came back home from an internship in a large IT company. As a souvenir, he brought back a band with a sequence of M natural numbers embroiled on it.

Vasya does not care much about numbers, so he wants to gift a band to a friend. However, each one of M Vasya's friends has exactly one number he strongly dislikes, and so would not want a band containing that number as a gift. All numbers disliked by Vasya's friends are different.

In order to still make a gift out of the band, Vasya wants to cut it in such a way, that every piece of the band could be given to at least one of his friends (several pieces may go to the same friend).

Your program must determine minimal number of cuts Vasya must perform to be able to give all pieces as gifts.

Input file format

First line of input file contains integer N — count of numbers on the band.

Second line of input file contains N integers a_i — a sequence of numbers on the band.

Third line of input file contains integer M — number of Vasya's friends.

Fourth line of input file contains M integers b_i — disliked number of i-th friend. All b_i are different.

Output file format

Output file must contain a single integer — minimal number of band cuts.

Constraints

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

Sample tests

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0

Problem D. Dissatisfied by spice ≡

Statement

Vasya became the chef of an elite restaurant. His clients are many and has very particular taste preferences. One of the most important features of restaurant dishes are various spices.

Each client requires specific amount of every kind of spice, according to his taste. If his dish does not contain enough of some spice, client becomes dissatisfied.

Since there is only a limited amount of each kind of spice in the kitchen, sometimes it is impossible to satisfy all clients. Your program must help Vasya to minimize number of dissatisfied clients.

Input file format

Input file contains integer number of kinds of spices M, followed by M integers A_j — amount of available spice of each kind.

Following is integer N — number of clients, and matrix P_{i j} — amount of spice of j-th kind required by i-th client. The order is: all spices for the first client, then all spices for the second client, etc.

Output file format

Output file must contain indexes of clients who will remain satisfied. Clients are indexed from zero.

Constraints

0 < M ≤ 5, 0 < N ≤ 50, 0 ≤ (A_j, P_{i j}) < 10

Sample tests

5
6 4 5 7 2

4
1 2 3 4 1
3 3 1 5 1
2 1 2 1 0
0 1 0 1 0

3
2
0

5
6 4 5 7 2

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

Problem E. Equipattern ≡

Statement

Young designer Vasya creates logo for his company. He imagines it to be a company name, each letter colored either blue or orange.

Vasya wants to color letters so that the name consisted of single-color substrings of equal length. Color of sequential substrings must alternate. In other words if first X letters are colored orange, next X must be colored blue etc.

For each letter of the alphabet, Vasya decided if it is allowed to be colored blue, orange, either of those colors, or not allowed to be used at all. Vasya wants to color company name in two colors so that his requirements for splitting into substrings and constraints on letter colors are satisfied.

Your program must calculate number of different ways Vasya may color his company name.

Input file format

First line of input file contains a string of letters which may be colored blue.

Second line of input file contains a string of letters which may be colored orange.

Third line of input file contains a string of letters — company name which must be colored.

Output file format

Output file must contain a single integer — number of different ways to color company name.

Constraints

All strings consist of small Latin letters. String length is not more than 10⁵.

Sample tests

a
b
abc

0

a
b
ab

1

Problem F. Food stalls ≡

Statement

City government plans to install several food stalls and several security posts on the street where young programming Alice lives. A scheme of their locations was developed.

Scheme is represented by a string S consisting of characters: '.' — unoccupied place, 'F' — food stall and 'S' — security post.

To be eligible for federal financing, plan must satisfy requirements of Federal program of Postponing and Stalling. In particular, a report is required, where for i-th security post there will be two numbers l_i and r_i — the number of stalls between this post and nearest post to the left (or the beginning of the street) and number of stalls between this post and nearest post to the right (or the end of the street).

Your program must generate the required report.

Input file format

The only line of input file contains a scheme with the plan.

Output file format

Output file must contain integer N — number of security posts, followed by N pairs of integers l_i and r_i — the number of food stalls to the left and to the right of i-th post. Posts must be listed in order of their occurrence in the scheme from left to right.

Constraints

Schema string is no longer than 10⁵.

Sample tests

.....FFF.F.F.FS......S..F.

2
6 0
0 1

S

1
0 0

Problem G. Grouping of cells ≡

Statement

There is a rectangular table with unsigned integer values in cells.

Initially table was stored on separate lines, however during the processing formatting was lost and all separators (including line feeds) were replaces by spaces (ASCII 32). It is known that values in every column were the same.

Your program must find possible number of rows for initial table.

Input file format

Input file contains a sequence of cell values, separated by spaces.

Output file format

Output file must contain all possible variants for number of rows, in increasing order.

Constraints

All cell values are in range from 0 to 2³¹ − 1.

Total number of cells is not greater than 2 ⋅ 10⁵.

Sample tests

10 12 10 12 10 12 10 12 10 12 10 12

1
2
3
6

10 12 10 12 10 12 10 10 10 12 10 12

1

Problem H. Hlelo? wrold ≡

Statement

Young programmer Vasya writes a "hello world" program in a simple programming language. Program consists of a single line and should look like that:

print("Hello,World")

Vasya is very bad at typing. While trying to enter the line above, he pressed letter keys L times, special character keys C times (including quotes, comma and parentheses). Vasya also pressed backspace key B times, erasing a single character every time.

Your program must determine if it is possible in principle that Vasya achieved the exact text above.

Input format

Input file contains integers L, C, B.

Output format

Output file must contain a single line YES or NO.

Constraints

0 ≤ L, C, B ≤ 100

L + C ≥ B

Sample tests

15 5 0

YES

2 7 6

NO

Problem I. Inner rotation ≡

Statement

There are two triangles attached to a fixed point F. One triangle in fully inside of another. Each triangle is represented by vertices in polar coordinate system (varphi, r) with the origin at point F.

It is known that internal triangle may rotate around the fixed point until it touches the external triangle.

Your program must determine maximum range of possible rotation angles for internal triangle.

Input file format

Input file contains 6 floating point numbers representing vertices of external triangle: varphi₁, r₁, varphi₂, r₂, varphi₃, r₃.

Followed by 6 floating point numbers representing vertices of internal triangle in similar manner.

Output file format

Output file must contain the width of range of allowed rotation angles in radians, with at least 5 correct digits after decimal point.

Constraints

All tests are designed to minimize errors due to machine loss of precision.

Both triangles are non-degenerate (vertices do not belong to the single line).

Fixed point F is inside of both triangles.

All angles varphi_i are in radians and in range from 0 to 2 ⋅ π.

Sample tests

2.10630 2.00000
6.05701 2.00000
4.00000 2.00000

0.00000 0.50000
1.57080 0.50000
3.92699 0.50000

6.28319

2.10630 1.23000
6.05701 1.50000
4.00000 2.00000

6.10430 0.40000
1.57080 0.40000
3.92699 1.60000

0.25326