Problem A. Alphabetic replacement ≡

Statement

You are given two strings of small Latin letters, S and T. Some letters of string S may be replaced by letters of T according to the following rules:

1. Each letter from T may be used only once or not used at all.
2. Letters from T must be used in order from left to right. In other words, if letter S_i is replaced by letter T_p, letter S_j is replaced by letter T_q, and i < j, then p < q.

You program must modify string S according to the rules above to get lexicographically smallest string.

Input file format

First line of input file contains string S. Second line of input file contains string T.

Output file format

Output file must contain optimally modified string S.

Constraints

0 < |S|, |T| ≤ 10⁵

Sample tests

aaa
abacaba

aaa

ababcaba
abca

aaaacaba

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. Cyclic state machine ≡

Statement

Vasya invented a device working similarly to finite automaton. Device accepts as input a cyclic string of characters, and has a pointer to one of characters. On each step the device reads the character at the current pointer position and executes an action according to a given table.

Action in the table is represented by four values S C Q H, where

• S — number of the current state of the device;
• C — character in the current position;
• Q — number of the next state of the device;
• H — number of characters to cyclically move the pointer (positive value — to the right, negative value — to the left).

The device will stop if:

• device will return to same position and same state as previously visited; or
• the table will contain no action for the current position and state.

Your program must, given input sting and a table, determine starting position and state which will cause device to execute maximum possible number of steps until stopping.

Input file format

First line of input file contains input string T, consisting of small Latin letters and digits. Second line contains integer M — number of commands. Following M lines contain commands in the format described above.

Output file format

Output file must contain two integers — numbers of staring position and starting state. Positions are numbered from zero. If there are several optimal solutions, output any of them.

Constraints

Action table contains no more than one action for each pair (position, state).

0 ≤ S, Q < 1000,

0 ≤ |H| ≤ |T|,

0 < |T| ≤ 500, 0 < M ≤ 36 ⋅ 1000

Sample tests

acabcbabac
4
1 c 2 -1
1 b 1 1
3 a 1 1
2 b 1 -1

2 3

9696969676
4
1 9 2 -3
1 6 2 2
3 7 1 1
2 6 1 -3

3 1

Problem D. Dense schedule ≡

Statement

One famous university has failed to create a proper schedule of classes before the beginning of the academic year. Teachers decided to fix this. They created a list of classes that teachers have to give to some of the groups of students according to the academic plan. However, coming up with an actual schedule is difficult and feels like something that a computer can do. They came to computer science department and asked you to write a program that will generate the best schedule.

There are N teachers numbered from 1 to N. There are M groups of students numbered from 1 to M. Teachers created a list of K pairs (t, g), meaning that teacher t needs to give a class to a group g. Some pairs may repeat in the list — this is because there might be several classes per day for the same subject (e.g., Calculus).

For simplicity, suppose that all these classes should happen in one day. The length of each class is the same and equal to the length of academic "pair" — a time slot. Of course, a teacher can not give two classes at the same time, as well as a group can not attend two classes simultaneously.

The best schedule is the one that fits into the minimum number of time slots. In other words, the schedule should ensure that the last teacher and the last group of students will leave the university as soon as possible.

Input file format

Input file contains integers N, M, K, followed by K pairs of integers t_i and g_i.

Output file format

Output file must start with an integer — the number of time slots in the schedule, followed by time slots description. Each description starts with l_i — the number of classes happening in this time slot, followed by (t, g) pairs from the original list.

The output must list all pairs from the input (∑l_i = K).

Constraints

1 ≤ N, M ≤ 100; 1 ≤ K ≤ 1000

1 ≤ t_i ≤ N; 1 ≤ g_i ≤ M

Sample tests

1 3 2
1 1
1 2

2
1
1 1
1
1 2

2 2 4
1 1
1 2
2 1
2 2

2
2
1 1
2 2
2
1 2
2 1

Problem E. 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 F. Fancy substring ≡

Statement

String T consists of small Latin letters. String P consists of small Latin letters and star symbols '*'.

Your program must find all positions in T where some cyclic shift of P occurs (that is, indexes s, for which there exists d such that P_{(i + d) mod |P|} = T_s + i, i = 0, |P| − 1).

Additionally, star in P may correspond to an arbitrary single character in T.

Input file format

First line of input file contains string T. Second line of input file contains string P.

Output file format

Output file must contain an integer K — number of positions, followed by K integers a_i — position indexes in ascending order. Positions are indexed from zero.

Constraints

1 ≤ |T| ≤ 10⁵

1 ≤ |P| ≤ 400

|P| ≤ |T|

Number of star symbols in P doesn't exceed 3.

Sample tests

abacaba
bca

1
3

abacaba
a*a

3
0 2 4

Problem G. 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 H. 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 I. 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 J. 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