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. Biota ≡

Statement

Young marine biologist Masha spent her summer in Primorye, diving and taking notes of what she saw on the seafloor. Later she found her records for one of the bays where she has been. These records were:

• A % of the seafloor is inhabited by starfish.
• B % of the seafloor is inhabited by sea urchins.
• C % of the seafloor is inhabited by shellfish.

Help Masha to figure the minimum possible percentage of the seafloor inhabited by all three species simultaneously.

In the first example, shellfish live everywhere. Starfish and sea urchins each take 3/4 of the seafloor, which means that at least half of the seafloor is inhabited by shellfish, starfish and sea urchins simultaneously.

In the second example, there are areas where 2 out of 3 species live. But it's possible that there are no areas where all 3 species live.

Input file format

Input file contains integers A, B and C.

Output file format

Output file must contain a single integer from 0 to 100 — the answer, in percents.

Constraints

0 ≤ A, B, C ≤ 100

Sample tests

75 75 100

50

30 45 40

0

70 80 90

40

Problem C. Easy patrol ≡

Statement

Young programmer Vasya tinkered with robots, and decided to create a new startup Easy Patrol with the goal of producing robot guardian to replace human guards.

As a first step, he considered a single wall of N meters in length and two patrolling robots moving back and forth along it.

First robot starts patrolling at the point located x meters from the left edge of the wall, moving to the right. Second robot starts patrolling at the point located y meters from the left edge of the wall, moving to the left.

Each second, events happen in the following order:

1. if robots are about to collide (that is, are facing each other at the distance 0 or 1 meters), both reverse direction.
2. each robot checks whether it has reached the edge and reverses direction if it is so.
3. both robots move simultaneously, each for exactly 1 meter in its current direction.

Your program must determine maximum possible distance between two robots.

Input file format

Input file contains integers N, x, y.

Output file format

Output file must contain a single integer — maximum distance between robots in meters.

Constraints

4 ≤ N ≤ 10⁶

0 ≤ x, y ≤ N

Sample tests

5 1 3

4

8 3 1

4

Problem D. Great triangle ≡

Statement

Consider a set of n points on a plane, described by their coordinates: M = {(x_i, y_i): i = 0, 1, …, n − 1}.

Your program must, given two points A and B, find a point C from set M, such that triangle {A, B, C} contains maximum possible number of points from M. Points both inside and on the edges of the triangle are counted.

Input file format

Input file contains integer n, followed by n pairs of integers — point coordinates (x_i, y_i). Next, four integers follow — coordinates of points A and B.

Output file format

Output file must contain a single integer — index of point C. Indexes start from zero. If there are several solutions, output any of them.

Constraints

Points A and B are different.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 0 < n ≤ 10⁵

Sample tests

10
-7683 -1465
 1000  6970
-1096 -1613
 7052  3877
-8237  2965
 5089  6152
-7697  5970
 1340 -7370
 2068  1467
 4499 -3269

 1990 -5786
-6140 -5000

5

10
-4036  1190
 4691 -1023
 7809 -1023
 7021 -6507
 4691 -1023
-1000 -5000
 3096 -1023
 1570 -4210
 7809 -1023
 7809 -1023

-7500 -5103
-1059 -1023

9

Problem E. Highway cycle ≡

Statement

Young programmer Vasya lives in a city where streets can be represented by a tree. Each vertex of a tree correspond to an intersection, each edge — to a street. So number of streets in the city is 1 less than a number of intersections. It is possible to get from from each intersection to every other one by streets.

There are two kinds of streets — residential and office ones.

City administration wants to create a looping road, represented by a cycle of streets. To minimize spending, only a single road of either kind must be built, creating a cycle. To satisfy zoning regulations, cycle must consist of at least 4 streets and number of residential streets in the cycle must be equal to the number of office streets.

Young programmer Vasya is preparing a presentation for city mayor and wants to add a slide with the total number of ways to add a street to the city road system, while satisfying all requirements. Your program must calculate that number.

Input file format

Input file contains integer N — number of intersections in the city, followed by N − 1 triplets of integers u, v, c — numbers of intersections connected by street (u, v) and the kind of the street. c = 0 — residential street, c = 1 — office street.

Output file format

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

Constraints

3 ≤ N ≤ 3000

0 ≤ u, v < N

Sample tests

4
0 1 0
1 2 1
2 3 1

1

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

2

Problem F. Interactive increment ≡

Statement

This is an interactive problem.

Jury has chosen a secret integer X consisting of exactly N bits. It is known that the number contains K bits '1' and N − K bits '0'. Your program can make queries of the form "+ Y", which causes current value of X to be increased by integer Y. Bits higher than N-th are truncated, so actual operation is X = (X + Y) mod 2^N.

Jury's program answers every query with number of '1' bits in the current value of X. Your program must determine current value of X by making no more than ⌊ N2⌋ queries.

Input format

First line of input contains two integers N and K — total number of bits in the value and number of '1' bits in the starting value.

Interaction protocol

To make a query, your program must output "+ Y", where Y — integer to be added to X. For every query jury's program will reply with a single integer — number of '1' bits in the value of X after executing the request.

When your program determines current value of X, it must output "! X" and stop.

If your program will make incorrect query, it will receive "Presentation error" verdict. If your program will exceed allowed number of queries, it will receive "Wrong answer" verdict.

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:

Constraints

1 ≤ N ≤ 60

0 ≤ K ≤ N

0 ≤ X, Y < 2^N

Note for samples

In the first sample jury has chosen number 13 (1101 in binary). After the first query the value is (13 + 9) mod 16 = 6 (0110₂). After the second query the value is (6 + 9) mod 16 = 15 (1111₂).

Sample tests

4 3 

2

4

+ 9

+ 9

! 15

2 2

! 3

Problem G. Jigsaw separation ≡

Statement

Rectangular jigsaw puzzle consists of two pieces. Each piece is a 4-connected set of square cells, each cell represented by character 'X' or 'O'.

Your program must determine whether it is possible to separate puzzle pieces by moving either of them in vertical or horizontal direction.

In the first sample it is possible to separate pieces by moving 'X' piece up and/or 'O' piece down.

Input file format

First line of input contains two integers W H. Following H lines contain W characters each — puzzle representation.

Output file format

Output must contain a single string YES or NO.

Constraints

1 ≤ W, H ≤ 100. Each piece contains at least one cell.

Sample tests

4 3
XXXX
XOXO
OOOO

YES

3 3
XXX
XOX
XXX

NO