Problem A. Amnesia ≡

Statement

Today, in a mathematics lesson, Timofey studied the topic of "Proportions". He was too lazy to write down his homework in his notebook, relying on his memory, and here is the result — Timofey remembers three of the four members of the proportion, but does not remember where they stood! He is also sure that the answer to the problem (an unknown element of proportion) is as a natural number. Help Timofey find all the correct answers for this assignment.

Input format

The first line of the input contains three integers separated by space: a, b and c — known members of the proportion.

Output format

Output natural numbers in ascending order  — all possible different solutions of the proportion. If there are no solutions — output the number -1.

Constraints

1 ≤ a, b, c ≤ 10⁹

Note on samples

In the first example, it is possible to make this proportion: 24 = 36.

In the second sample, there are no suitable solutions (with an integer answer).

In the third sample, it is possible to make these proportions: 24 = 816, 24 = 48, 12 = 48.

Sample tests

2 3 4

6

2 3 5

-1

2 4 8

1 4 16

Problem B. Bouncing pairs ≡

Statement

Let there be two strings A and B, consisting of digits and lowercase Latin characters.

On the string A, we define the operation textSWAP(i, i + 1), which consists in exchanging the characters at positions i and i + 1.

It is required to determine the minimum number of such operations for transforming string A to string B.

Input format

Input contains two strings: A and B.

Output format

Output must contain a single integer.

Constraints

It is guaranteed that the required transformation can be performed.

Line lengths do not exceed 2 ⋅ 10⁵.

Sample tests

abababababab
babababababa

6

abc
bca

2

Problem C. Confections ≡

Statement

Today is Grisha's birthday! Each of his n friends brought a box of favorite sweets as a gift to the birthday boy. Since Grisha is not a greedy boy, he took all the sweets out of the boxes and put them on n + 1 plates and placed them in front of each guest (including himself). To everyone's delight, this was done without a remainder. Immediately after that, his mother returned from work and it was decided to put all the sweets on n + 2 plates. To everyone's surprise, this division was completed without a remainder.

Given the known number of sweets in one box k, determine the possible number of guests at the party.

Input format

The only line of the input contains a natural number k.

Output format

In the first line output single natural number g — the number of possible answers to the problem's question. In the second line print g natural numbers — possible number of guests in ascending order, separated by a space. It is guaranteed that there is at least one suitable answer.

Constraints

1 ≤ k ≤ 10⁹

Notes on sample

In the sample, the number of candies in one box is 6.

If one guest came to Grisha, then the total number of sweets is also 6. It is easy to divide them equally without a remainder both into two and three plates.

If two guests came to Grisha, then the total number of sweets is 12. It is easy to divide them equally without a remainder both into three and four plates

There are no other solutions.

Sample tests

6

2
1 2

Problem D. Disordered polygon ≡

Statement

Zhenya drew a regular n-gon on the board, labeled its vertices with numbers clockwise in ascending order: "1 2 3 ... n". Nikita came up and rearranged the numbers in the signature, erased all sides of Zhenya's figure and connected the vertices in the resulting new order (including the first and last vertices). Now a closed broken line flaunts on the board. How many pairs of line segments intersect?

Input format

The first line of the input contains single integer n. The second line contains n numbers a₁, a₂… a_n — a permutation of the polygon's vertices.

Output format

Output a single non-negative integer — the answer to the problem question.

Constraints

3 ≤ n ≤ 10⁵

Note on samples

Sample tests

4
1 2 3 4

0

4
1 2 4 3

1

5
2 4 5 3 1

2

8
5 6 1 3 4 7 8 2

8

Problem E. Empty rectangles ≡

Statement

Consider a set of N two-dimensional points represented by their coordinates (X_i, Y_i).

It is required to determine the number of all possible rectangles that satisfy the following conditions:

• the vertices of the rectangle must belong to the original set of points,
  and its sides must be parallel to the coordinate axes;
• among the remaining points, none should lie on the border or inside such a rectangle;
• the rectangle must be non-degenerate (have a non-zero area).

Input format

Input starts with integer N,
followed by 2 × N integers, representing point coordinates: X_i, Y_i.

Output format

The output should contain
the number of detected rectangles.

Constraints

All input points are different.

 − 10⁶ ≤ (X_i, Y_i) ≤ 10⁶,

4 ≤ N ≤ 10⁵

Sample tests

12
-35 -17
 43  10
 24 -17
-16 -29
 43  54
-35  40
 43 -29
 24  10
-16  54
-35  10
 43 -17
 24  40

3

12
-20 -34
 17  34
-20  40
-10 -20
-43 -17
 19  15
-15  16
  0 -34
-32  19
  0 -12
-13   0
  0  40

0

Problem F. Fast battlepass ≡

Statement

Paulundra is playing a multiplayer shooter called Counter-rant. Recently Counter-rant launched a new season of the Battle Pass where you can get n of the m available weapon skins. The skin opening system is unusual: the player is given n runes, to use the rune, you need to insert two crystals of fixed colors into it, after which if the rune fits the weapon, the weapon opens. A rune matches a weapon if the weapon contains both colors contained in the rune. Each weapon skin contains exactly C colors.

The Battle Pass consists of k levels. For each level of the Battle Pass, exactly one crystal is given, for each level the reward is known in advance. For reaching level i, the reward will be a crystal with the color a_i. The player uses the crystals at his own discretion: inserts into any of the runes or does not use the crystal at all. Since it's hard to earn levels, Paulundra wants to know what is the minimum number of Battle Pass levels she needs to unlock in order to get at least p skins, assuming she distributes crystals and runes optimally.

Input format

The first line of the input contains five numbers m, C, n, p and k. This is followed by m lines containing C numbers c_ij each describing the colors of weapon skins with number i. The next n lines contain two numbers each a_i1 and a_i2  — rune descriptions. The last line of the input contains k number S_i, where S_i is the color of the crystal for getting level i

Output format

Print a single integer  — the minimum number of levels you need to get to open at least p skins. If p skins cannot be opened print -1.

Constraints

1 ≤ m ≤ 100

2 ≤ C ≤ 10

1 ≤ n, p ≤ 10

1 ≤ k ≤ 10⁶

1 ≤ a_i1, a_i2, S_i, c_ij ≤ 10⁹

a_i1 ≠ a_i2

Sample tests

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

8

1 2 1 1 1
100 100000
1 2
1

-1

3 2 4 1 5
2 1
3 1
8 8
1 2
1 3
3 4
1 2
1 2 3 1 2

2

Problem G. Graphword ≡

Statement

Vasya found out that his grandfather has been fond of solving crossword puzzles for a very long time.

On his anniversary, Vasya decided to present him a game, which is a generalized version of the crossword puzzle — "graphword".

A playing field in it is an undirected graph the vertices of which are assigned lowercase letters of the Latin alphabet.

In the process of solving the "graphword" the player needs to compose words by moving along the edges of such a graph.

According to the rules of the game, each edge can be visited more than once.
However, it is forbidden for the current edge to coincide with the previous one.

When developing levels for his game, Vasya was faced with the task of determining the number of all possible paths,
forming some given word in a given graph.

Since the resulting number may be too large, the answer should be the remainder of its division by 10⁹.

Input format

Input starts with the number of vertices N, followed by the set of characters assigned to each of the vertices.

Next, the number of edges M is given, followed by the edges themselves,
each of which is given by the indices of its vertices: a_i, b_i. Vertices are numbered starting from zero.

Input is finished with the string W, for which calculation should be done.

Output format

Output must contain a single integer.

Constraints

1 ≤ N ≤ 10⁴, 0 ≤ M ≤ 10⁴, a_i ≠ b_i, 1 ≤ |W| ≤ 10

Sample tests

6
a b c a b c

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

abba

4

6
a b c a b c

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

abc

5

Problem H. Health and light 2 ≡

Statement

The city of N has a happy event! On the single street of the city, new street lamp will be installed and the new pharmacy will open. Help the city governor to find optimal places for these objects.

The street is represented by a segment of coordinate axis, where the leftmost house has coordinate 0. Let's assume house sizes to be negligibly small compared to the street length and represent houses as points on the axis.

The lamp has "brightness" parameter expressing the distance from the lamp where the light reaches. For example when brightness is equal to 10, lamp installed at the point x = 25 will light the street on the segment from 15 to 35 inclusive.

The pharmacy has "remoteness" parameter expressing the distance from it to the house such that people from that house will still visit. For example when remoteness is equal to 100, pharmacy located at point x = 25, will be visited by people living in houses with coordinates from 0 to 125 inclusive (there are no houses with negative coordinates).

Input format

First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. The second line contains non-negative integers x_i — coordinates of each house in ascending order.

Output format

Output a single non-negative integer — maximum total number of houses illuminated by the lamp and convenient to visit pharmacy from. Both lamp and pharmacy may be located at points with the coordinate of some house.

Constraints

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i ≤ 10⁹

Notes on sample

Sample contains ten houses, lamp brightness is 15 and pharmacy remoteness is 20. Lamp can be installed, for example, at point 115 (three houses will be illuminated: 100, 110 and 120). Pharmacy may be located at point 20, in which case it can be visited by people from the first 5 houses. A greater number of houses having "access" to the lamp and pharmacy cannot be obtained.

Sample tests

10 15 20
0 10 20 30 40 60 70 100 110 120

8

Problem I. Interactive circles ≡

Statement

The problem is interactive and involves interacting with the jury program by sending and receiving messages in specific format.

Let there be a two-dimensional point, it's known that the point is located inside a circle with radius 1.0 and the center at axes origin.

You're allowed to send queries in the form "check if circle with a center (x, y) contains the given point".

For the first query circle radius is 0.9. For each of the next queries the radius is reduced by 0.1.

You are to send exactly 8 queries in such a way, that the last one contains the point in question.

Interaction protocol

For each query print to output stream (stdout) two numbers (x, y) specifying the circle center.
Do not forget to flush the stream after each query.

As a response input stream (stdin) will receive a single integer:
1 — the circle contains the point; 0 — otherwise.

Constraints

For the program to work correctly a line break
should be output and flush
should be performed
after each query sent to the output thread.

Problem J. Journey back home ≡

Statement

Student Vasily, having returned to his home village for the holidays, celebrates his successfully passed exams on a grand scale. He's walking along a single street, the schematic of which is shown on the picture. The street has a houses (with numbers 1, 3, 5, …, a × 2 − 1) on the left and b houses (with numbers 2, 4, 6, …, b × 2) on the right. There's a huge puddle in the middle of the street, so one can only cross the street at either start or end of it.

Standing next to a house in an altered state of mind Vasily randomly decides where to go next (each of the two possible directions is chosen with the probability 12). If he finds himself next to a tavern (house with the number t), he will immediately walk in and continue to party till morning, but if he is next to his home (house with the number h), he will decide that this is the sign of fate and he is to stop having fun. What is the probability that Vasily reaches his home and stops the celebration if currently he's standing next to the house with number n?

Input format

The first line of input contains two natural numbers separated by space: a and b — street description. The second line contains three natural numbers t, h and n separated by space — houses description. The consistency of the input data is guaranteed. It is guaranteed that the numbers t, h and n are distinct.

Output format

Output two space-separated natural numbers — the numerator and denominator of the irreducible fraction expressing the probability of the described event.

Constraints

1 ≤ a, b ≤ 10⁹

1 ≤ t ≤ a × 2 − 1, if t is odd.

2 ≤ t ≤ b × 2, if t is even.

Constrains for t are similar to h and n.

Notes on the sample

See picture. The street in the sample only has three houses (with number 1, 2 and 3). Houses on the left side have numbers 1 and 3, while on the right side there's only one house with the number 2. In this sample one it's possible to walk from any house to any other house. Vasily can reach either his home or tavern with equal probability 12.

Sample tests

2 1
1 2 3

1 2

Problem K. Keep on doing! ≡

Statement

The expression n − (n − 1) − (n − 2) − (n − 3) − ...  − 3 − 2 − 1 is written on the board (for example, if n = 5 it will be written as 5 − 4 − 3 − 2 − 1). To avoid a failing grade in mathematics, Gavrila needs to put left and right parentheses in this expression, so that the result is zero. How many ways does he have to do it?

Input format

Input contains natural number n.

Output format

In the first line output a non-negative integer m — the number of ways to arrange the parentheses in the required way. In the next m lines print two space-separated natural numbers a and b — the position of the parentheses (numbers from a to b inclusive will be inside the brackets). Output numbers a and b in descending order, and output pairs of numbers in order of descending a.

Constraints

4 ≤ n ≤ 10⁵

Note on samples

In the first example, n = 5 is given. Unfortunately, Gavrila won't succeed, for the given n there is no way to place the brackets in the required way.

In the second example n = 7 is given. If all numbers from 5 to 3 are enclosed in brackets, then an expression with the desired value will be obtained: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

In the third example, for n = 12 there are several ways to solve the problem.

Sample tests

5

0

7

1
5 3

12

2
11 8
8 2