Problem A. Avengers and Shawarma ≡

Statement

Avengers defeated alien invaders and decided to eat some shawarma.

Hulk ordered N shawarmas. M shawarmen immediately started to cook his order. Each shawarman can cook his first shawarma in T minutes. Each next shawarma requires S minutes more to cook than the previous one.

HULK SMASHes!!! awaiting his shawarmas.

You should help Avengers to find out the time when all shawarmas ordered by Hulk will be ready and green giant will calm down. Of course, Jarvis could solve this task, but Iron Man's suit is broken and only air conditioner is working right now.

Input format

First line contains two integers N and M — number of shawarmas ordered by Hulk, and number of shawarmen who are going to complete his order.

Second line contains two integers T and S — time needed to cook the first shawarma and the difference of cooking time between two shawarmas in the row.

Output format

Print one integer — time needed to complete Hulk's order.

Constraints

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

Sample tests

5 2
10 5

45

13 4
4 1

22

10 1
5 0

50

Problem B. Bedtime thoughts ≡

Statement

When Anastasia was a child, she often saw highlights moving on the celling of her room. These highlights became especially visible at night, when Anastasia was lying in her bed, looking at the celling. As she got older she understood, that the reason of the highlights were headlights of automobiles, driving to the yard.

Today Anastasia's husband presented her a car. She is interested if her new car could light up her room.

Windows of Anastasia's room are at height of H meters. You can assume that room is lighted up if any part of the window is lighted up.

Light of the headlights forms a sector of a circle. The range of her car's headlights is L meters. The maximum angle of light spread is A degrees.

The yard can be considered as a horizontal surface. The height of the car is negligible.

Input format

The first line contains three integers H, L and A.

Output format

Print "Yes" or "No" (without quotes) — Can Anastasia's new car light up her room?

Constraints

1 ≤ L, H ≤ 100

0 < A < 90

Sample tests

25 50 30

Yes

25 45 30

No

9 10 89

Yes

Problem C. Casino ≡

Statement

Aningaaq and his N brothers went to a casino. Today they are going to play following game. First they agree about their bet. They can't change this bet later. The game consists of several rounds. Each round, every player is going to bet or to pass. Winner is somehow determined and receives some prize (not money).

The oldest brother got the largest amount of money from parents. The second oldest brother got one dollar less than the oldest brother. The third oldest got two dollars less than the oldest brother. And so on. Aningaaq is the youngest brother. He got only M dollars.

Brothers are going to play while somebody has any money. And they are not supposed to give money to each other.

Aningaaq is worried that game can last very long and they are going to be late at home. Help him to find out the minimal possible number of rounds.

Input format

First line contains two integers N and M — number of Aningaaq's brothers and amount of money Aningaaq has.

Output format

Print one integer — minimal possible number of rounds.

Constraints

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

Sample tests explanation

In the first test Aningaaq is alone, so he can bet all his money in the first (and single) round.

In the second test Aningaaq has 1 dollar. His brother has 2 dollars. Brothers can agree that the bet is one dollar. Then, in the first round Aningaaq will spend all his money and his brother will have one more dollar to play another round.

Sample tests

0 2

1

1 1

2

Problem D. Don't understarve ≡

Statement

Wilson got lost in a cave N × M cells. However, he has a map with the following notation keys:

'#' — an impassable cell (an abyss, a wall);

'.' — a free cell;

'X' — a wormhole — Wilson can teleport from this cell to any other wormhole with an equal probability;

'S' — a start cell;

'F' — a target cell — Wilson needs to get to this cell (an exit to the surface).

Movement through a wormhole is a risky process, because it takes a lot of Wilson's mind. When the level of his mind become too low, Wilson can be attacked by monsters.

Wilson's mind will be enough exactly for one teleportation. Therefore he wants to know the probability of him getting out of the cave using no more than one wormhole. Naturally, Wilson moves optimally, trying to maximize this probability.

Wilson can move in four directions: up, down, to the right and to the left.

Note that Wilson cannot step into a cell with a wormhole without using it.

Input format

The first line contains two integers N and M — dimensions of the cave.

It follows by N lines, M characters each — map of the cave.

It is guaranteed that there is one 'S' cell, at least one 'F' cell and at least two 'X' cells on the map.

Output format

Print the answer as an irreducible fraction by two integers (for example: if the answer is 50 / 74, you have to print "25 37").

Constraints

2 ≤ N, M ≤ 1000

Sample tests

2 2
XX
SF

1 1

4 4
#F.X
##X#
X#SX
###F

2 3

2 5
.F#S.
XXXXX

1 2

3 5
.F#S.
.#X#.
X..X#

0 1

Problem E. Encrypted phone ≡

Statement

This is an interactive problem.

As a punishment for Aleksey using his cellphone in the classroom, the teacher locked Aleksey's device with a password. This password is a sequence of N unsigned integers X_i, chosen by the teacher. However, the teacher did not want to waste his time for thinking up all numbers of the sequence. Therefore, he used a random number generator.

To unlock his device, Aleksey needs to guess the sequence. He can ask the teacher no more than Q questions: whether X_i is divisible by d. All numbers in the sequence are indexed from 1 to N.

Help Aleksey to regain access to his cellphone. He has already regretted his bad behavior during the class. He'll never do it again.

Input format

The first line contains one integer N — the length of the sequence.

It is guaranteed that the sequence is randomly generated before all Aleksey's questions and cannot be changed after that.

Output format

To give your answer to the teacher you have to print character "!" (without quotes), then print N space-separated guessed numbers X_i. Note that "!" and X₁ should be separated by a space too. Your program should terminate immediately after you gave the answer.

Interaction

Jury has fixed a number Q for each test — the maximum amount of questions, which you can ask the teacher. It is guaranteed that Q questions are enough to solve the problem. Q won't be given to your program as an input. If your solution asks more than Q questions, it will get "Wrong answer" for this test.

To ask a question your program has to print line "? i d" (without quotes), i (1 ≤ i ≤ N) and d (1 ≤ d ≤ 5000) are integers. Jury program gives your solution line "Yes" if X_i is divisible by d or "No" if it's not.

In the end of each question you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):

Constraints

100 ≤ N ≤ 400

1 ≤ X_i ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 10⁴)

Sample tests explanation

Note that the first test doesn't satisfy the constraints of the problem (N = 2).

It was created only to demonstrate interaction of solution program and jury program.

Q = 2000 for the first test.

Sample tests

2

Yes

No

Yes

No

No

Yes

Yes

Yes

Yes

Okay

? 1 3

? 1 5

? 1 7

? 1 11

? 1 13

? 1 4998

? 2 128

? 2 512

? 2 4096

! 4998 4096

Problem F. Factorio ≡

Statement

Leonid is an astronaut. His spaceship crashed on far unknown planet, full of natural resources. Leonid couldn't repair his spaceship, therefore he stayed on the planet. Many years later he achieved fantastic progress in planet exploration — he built an ore mining and processing mill.

The mill works in several stages:

1. N drills mine the ore. The speed of one drill is U_N kilograms per hour;

2. The ore gets to melting furnaces. The speed of one furnace is U_K kilograms per hour;

3. After furnaces, plates get to M machine-tools. The speed of one machine-tool is U_M kilograms per hour.

Leonid's mill pollutes the planet. This pollution disturbed inhabitants of the planet. Fictional arthropods have broken all furnaces.

Leonid is planning to build new furnaces and to renew manufacture. But at first he wants to calculate an optimal number of furnaces. We will call "surplus" the total quantity of the ore and plates, which is waiting for the processing. The number of furnaces is optimal if the surplus is minimal for the fixed period of time.

Help Leonid to calculate optimal number of furnaces. Obviously, Leonid wants to renew manufacture as fast as possible. Therefore among all possible answers, you should choose the minimal one.

Input format

The first line contains two integers N and M — the number of drills and machine-tools respectively.

The second line contains three integers U_N, U_K and U_M — the speeds of one drill, one furnace and one machine-tool respectively.

Output format

Print an integer — optimal number of furnaces.

If there are several possible answers, choose the minimal one.

Constraints

1 ≤ N, M, U_N, U_K, U_M ≤ 10⁹

Sample tests explanation

Let's consider first test. Let's fix the period of time — T = 10 hours. Amount of produced resources is shown in the table.

Surpluses are equal for three and four furnaces, which means that three furnaces is enough.

Sample tests

10 7
1 3 1

3

6 4
2 5 3

3

13 11
2 6 3

5

Problem G. Gandalf and Trolls ≡

Statement

Trolls surrounded Gandalf the Grey in a cave. Initial distance between the wizard and the nearest troll is R meters. Trolls run T meters every second. At the end of each second Gandalf throws the trolls back to D meters by the magic ring of light.

But there is a problem — angry Saruman the White cursed Gandalf's staff, and now it works only with some probability P.

The trolls will turn into the stone when sunshine lights up the room. Gandalf needs to know how many chances he has to stay alive until the sunrise. Sunrise time is S seconds. Gandalf will die if the distance between him and trolls become less than 1 meter before sunrise.

Input format

The first line contains four integers R, D, T, S.

The second line contains a real number P. P is given with at most 5 digits after the decimal point.

Output format

Print a real number — probability that Gandalf will stay alive until dawn.

Your answer will be accepted if it has absolute error at most 10^− 5. More specifically, if your answer is a and the jury answer is b, your answer will be accepted if |a − b| ≤ 10^− 5.

Constraints

1 ≤ R ≤ 50000

1 ≤ D, T ≤ 100

1 ≤ S ≤ 500

0 ≤ P ≤ 1

Sample tests

10 10 10 1
1.0

0.00000

15 6 10 2
0.7

0.70000

7 1 2 3
0.0

1.00000

50000 100 100 500
0.0

0.00000

100 99 1 500
0.01

0.33301

Problem H. Hydrocarbons ≡

Statement

A group of scientists studied a sample of vanadium catalyst of new generation. It allows to form different linear hydrocarbons from gaseous mixture of carbon and hydrogen.

Hydrocarbon with a certain structure became the result of each scientists experiment. His formula was recorded by spectral analysis device as a linear line. However, such form of record is short. Therefore, scientists needed to transform this record to the full version.

The full version of any hydrocarbonic chain, received in this experiment, is formed by the following rules:

1. The hydrocarbonic chain is pictured as a linear sequence of carbons (pictured by symbol 'C'). The link between carbons can be single (pictured as '-') or double (pictured as '=').

2. Each carbon is connected with hydrogens by single links, to be tetravalent. This means that each carbon should have 4 links (double link is counted as two links):

 — first and last carbons are connected to form equal angles. Namely, if there are two hydrogens they are connected by diagonal links ('/', '\'). If there are three hydrogens they are connected by up ('|'), down ('|') and side ('-') links.

 — the rest of carbons: single hydrogen is connected by up link and two hydrogens are connected by up and down links.

Short version of hydrocarbonic chain looks like a sequence CHa₁ CHa₂...CHa_N, where a_i (2 ≤ a_i ≤ 4) is a number of hydrogens with i^th carbon. There is no number when it's only one hydrogen. And there is no 'H' symbol when carbon does not have any hydrogens.

Note that short record should have the same orientation as full record. Which means that the leftmost hydrocarbon in short record should match the leftmost hydrocarbon in full record.

Look carefully at sample tests for complete understanding.

Input format

First line contains a string with short version of hydrocarbonic chain.

It is guaranteed that given hydrocarbonic chain is correct.

Output format

Print 5 × (3 + 2 ⋅ N) characters, where N is the number of carbons in given chain.

All spaces not occupied by symbols of links or atoms should be filled with symbol '.'.

Constraints

1 ≤ N ≤ 10000

Sample tests

CH4

..H..
..|..
H-C-H
..|..
..H..

CH2CH2

H.....H
.\.../.
..C=C..
./...\.
H.....H

CH3CH2CH2CH3

..H.H.H.H..
..|.|.|.|..
H-C-C-C-C-H
..|.|.|.|..
..H.H.H.H..

CH3CHCCH2

..H.H.....H
..|.|..../.
H-C-C=C=C..
..|......\.
..H.......H