Problem A. Attacking rooks ≡

Statement

A pawn is located on a chess board at coordinates x, y (x is a column number, y is a row number).

You must write a program to determine maximum number of rooks which can be placed on this board so that not a one of them will attack another.

Input format

Input contains integers x and y.

Output format

Output must contain a single integer — maximum number of rooks.

Constraints

1 ≤ x, y ≤ 8

Sample tests

1 1

8

Problem B. Back from the future ≡

Statement

Kolya Gerasimov was born on January 1st, 1970. After visiting his strange neighbor's apartment on April 11th, 1982, he found a time machine and travels exactly 100 years into the future (that is, he goes to April 11th, 2082).

After living in the future for exactly a years, Kolya uses the same machine to go back to the past, where he lives normally, collecting precious archive data for future historians. After exactly b more years after his return, Kolya makes the final travel for exactly 100 years into the future. Then he lives in the future without aging due to amazing achievements of future medicine.

How many full years did Kolya Gerasimov live at January 1st of year n?

Input format

Input data contain three natural numbers: a, b and n.

Output format

Output data must contain a single integer — full years lived by Kolya on January 1st of the given year. If at the given date Kolya was not present in that moment of time, output  − 1.

Constraints

2 ≤ a + b ≤ 99

1971 ≤ n ≤ 3000

Note on samples

In both samples Kolya lived in the future for 12 years, got back, and after 27 years went to the beautiful faraway again. Time line for the life of Kolya is given on a picture. For January 1st, 2088 he lived 18 full years. However, on January 1st 1988 he was in the future.

Sample tests

12 27 2088

18

12 27 1988

-1

Problem C. Circulation of try-square ≡

Statement

During a woodwork lesson at school, Timofey got his hands onto the try-square with wooden handle and metallic blade. Since Timofey has already finished his assignment (producing a stool), he started to roll the try-square along the coordinate axis. Starting position and movement direction are shown on the picture.

Your program must, given the coordinate of the point on the axis, determine which part of the try-square touched it.

Input format

Input contains three integers a, b and n — lengths of the wooden and metallic internal sides of the try-square and the coordinate of point. It is guaranteed that a and b are catheti of Pythagorean triangle (that is, hypotenuse is a whole integer).

Output format

Output must contain a single word:

• wood, if point is touched by the wooden handle,
• metal, if point is touched by the metal blade,
• empty, if point is not touched by the try-square.

Constraints

3 ≤ a < b ≤ 1000

1 ≤ n ≤ 10⁹

Sample tests

3 4 11

wood

Problem D. Discount season ≡

Statement

Vasya has heard that the discount season has started in a shop nearby.

For a single visit to the shop buyer tries to purchase as many items as possible with total weight not greater than W_max, to be able to carry them out with him. There is just one item of every type in the shop. According to discount rules, one client is allowed no more than 3 visits.

You must write a program to calculate optimal sequence of purchases allowing to buy maximum number of items. Total cost of all items must not exceed P_max — the amount of money Vasya has. If several variants with maximum number of items exist, choose one with minimal number of visits.

Input format

Input starts with total number of items n, followed by n pairs of integers: P_i — price of i-th item, W_i — its weight.

Next in the input data are maximum allowed amount of money P_max (total for all visits) and W_max — maximum weight Vasya is able to carry in each visit.

Output format

Output must contain optimal sequence of purchases, described as follows.

First, a total number of visits Vasya has no make. Then for each visit: count of items purchased, followed by item numbers in any order. Items are numbered starting from zero.

If there are several optimal solutions, output any of them.

Constraints

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

Sample tests

12

10 2
10 2
10 8
10 2
5 3
10 2
1 7
10 2
10 4
10 2
1 3
10 2

100 10

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

10

4 1
5 2
1 3
8 2
7 1
5 2
8 3
7 1
5 1
6 8

24 8

1
5 0 1 2 4 8

Problem E. Enforcing nine ≡

Statement

There is an array of integers a_i. You can choose any single element and replace any single decimal digit of it with any other one. Cost of such replacement is equal to absolute value of the difference between digits.

Your program must find such a replacement of single digit in a single element that the decimal representation of the sum of all elements will contain at least one digit 9, or determine that it does not exist. The cost of chosen replacement must be minimal possible.

Leading zeroes are not eligible for replacement.

Input format

Input contains integer N — array size, followed by N integers a_i.

Output format

Output three integers: element number, number of digit to be replaced and the digit to replace with.

Elements and digits are numbered starting with 0. Digits are numbered right to left.

It is guaranteed that sum of elements of the input array does not contain digit 9.

If required replacement does not exist, output  − 1. If there are several solutions, output any of them.

Constraints

1 ≤ N ≤ 100000

|a_i| ≤ 10⁹

a_i ≠ 0

Sample tests

1
1

0 0 9

3
11 1 31

0 1 6

2
-8 8

-1

Problem F. Fractional multiplication ≡

Statement

There is a set of N rational fractions, each is represented by corresponding numerator A_i and denominator B_i.

You must write a program that outputs:

• 0 — if the product of all fractions is either 1 or a prime;
• 1 — if it is integer non-prime;
• 2 — if it is a fractional number.

Input format

Input contains integer N, followed by N pairs of integers (A_i, B_i).

Output format

Output must contain a single integer — answer to the problem.

Constraints

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

Sample tests

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2

Problem G. Geometric similarity ≡

Statement

There are two simple (without self-intersections) polygons, each represented by a sequence of vertices in either clockwise or counter-clockwise order.

Your program must determine whether the polygons are similar, that is, whether one of them can be transformed into another by applying zero or more of the following operations:

• scaling all edges by a non-zero constant;
• rotating by 90^∘ in any direction around some fixed point;
• translation (offset by a vector);
• orientation changing (from clockwise to counter-clockwise and vice-versa).

Input format

Input contains integer n, followed by 2 ⋅ n vertices (first one polygon, then another), represented by pairs of integers: (x_i, y_i).

Output format

Output must contain a single integer: 1, if polygons are similar, 0 otherwise.

Constraints

It is guaranteed that both polygons are non-degenerate, i.e. have an area strictly greater than zero.

All edges also have non-zero length.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10⁵

Sample tests

5
-300 300
-100 500
 200 400
 200 200
-100 100

 250 120
 150 220
  50 120
 100 -30
 200 -30

1

5
 100 200
   0 400
 300 300
 300 100
   0   0

 350 150
 150 320
  50 220
 100   0
 200   0

0

Problem H. Hereditary string ≡

Statement

Vasya got a text string S as an inheritance from his grandmother. Vasya decided to play with this string.

On each step, Vasya picks a symbol and replaces every occurrence of this symbol with a space. Conversely, if this symbol is already replaced by space, Vasya replaces each of corresponding spaces back with the original symbol in the same position.

Your program must, after each step, determine the number of words (substrings of consequential non-spaces) currently present in the string.

Input format

First line of input contains string S. Following line contains string T, representing a sequence of symbols chosen by Vasya.

Strings consist of digits, small and capital Latin letters.

Output format

Output must contain a sequence of integers N_i — number of words in string S after step i.

Constraints

Symbol case does matter, i.e. small and capital letters are considered different.

1 ≤ |S| ≤ 10⁷, 1 ≤ |T| ≤ 10⁴

Sample tests

1a2b3c4d1a2b3c4d
1234abcd

2
4
6
8
6
4
2
0

ababbcc11a2AAcc3
abca1234

3
2
3
4
4
5
4
4

Problem I. Indices symmetry ≡

Statement

Young programmer Vasya develops a data storage with a programming interface of multi-dimensional array. Elements of this array are accessed by composite index: (i₁, i₂, …, i_N). Array dimensions are defined by values A₁, A₂, …, A_N (i.e. 0 ≤ i_k < A_k, k = 1… N).

Index ranges are non-decreasing (A_k ≤ A_k + 1). A special feature of Vasya's array is index-permutation symmetry. It means that elements with composite indices coinciding up to their permutation are considered equal.

To compactly represent array in memory Vasya decided on the following layout. Elements are stored sequentially row-by-row (aka row-major order) in one-dimensional array, which corresponds to lexicographically increasing composite indices. Those elements for which some permutation of their composite index was already encountered before are skipped.

Your program must execute queries of two kinds.

• Given composite index, determine corresponding one-dimensional index.
• Given one-dimensional index, determine corresponding composite index.

Input format

Input data starts with an integer N — number of array dimensions.

Followed by N integers A_j — array sizes in each dimension. Next are integer M and M query descriptions, one per line. Queries are of two kinds:

• Character f, followed by N integers (i₁, i₂, …, i_N) — composite index.
• Character b, followed by an integer — one-dimensional index.

Output format

Output must contain a sequence of integers — result of execution for each query in the order of input. Elements of composite indices must be sorted in ascending order.

Constraints

Indexing of both one-dimensional and multi-dimensional arrays starts with zero.

0 ≤ i_j < A_j ≤ 100, A_j ≤ A_j + 1, 1 ≤ N ≤ 10, 1 ≤ M ≤ 10⁵

Sample tests

5 5 5 5 5 5

8
f 4 4 4 4 4
f 0 1 2 3 4
b 125
f 0 1 1 2 2
f 3 1 4 0 2
b 100
b 49
b 0

125
49
4 4 4 4 4
39
49
1 3 3 3 3
0 1 2 3 4
0 0 0 0 0

5 1 2 3 4 5

8
f 0 1 2 3 4
b 27
f 0 1 0 1 3
b 41
b 1
f 0 1 1 2 3
f 0 0 0 0 0
b 0

41
0 0 2 3 4
16
0 1 2 3 4
0 0 0 0 1
33
0
0 0 0 0 0

Problem J. Just do it! ≡

Statement

All you need to do is to output all possible variations of the phrase Just do it!, differing only by the case of some letters (for example jUst DO it!).

Output format

Output must contain all possible variations of the phrase, one per line. Order of lines is not important.

Problem K. Kit of circuits ≡

Statement

You are to make a circuit using ∑ni = 1k_i given parts, so that circuit has the maximum possible number of free outputs.

There are n different types of parts: each type is characterized by the number of inputs (a) and outputs (b). Any input can be connected to any output. Unused outputs are called free outputs. When connecting a part to the circuit it is mandatory to use all inputs of this part.

The final circuit must have exactly one input so that you can connect the circuit to a single output source.

Input format

The first line contains an integer n — the number of part types.

The next n lines contain three integers k_i a_i b_i — the number of parts of i-th type and a description of these parts.

Output format

Output must contain a single integer: the maximum possible number of free outputs after assembly and connection of the circuit to the source. The final circuit may not contain any parts, then only the source output is free.

Constraints

0 ≤ n ≤ 10⁶

1 ≤ k, a, b ≤ 10⁶

Sample tests

4
1 3 4
2 1 2
1 7 8
1 1 3

6

3
1 3 4
1 5 6
3 7 7

1

Problem L. Limited permutation ≡

Statement

There are two integer arrays A and B, of length N each.

Your program must generate lexicographically minimal permutation of A, satisfying conditions:

A_i ≤ B_i, i = 1, 2, …, N

Input format

Input contains integer N, followed by 2 ⋅ N integers: array A, then array B.

Output format

Output must contain N integers — resulting permutation.

If the solution does not exist, output a single number  − 1.

Constraints

0 ≤ A_i, B_i ≤ 10⁹, 1 ≤ N ≤ 2 ⋅ 10⁵

Sample tests

5
1 9 3 7 5
9 3 9 1 9

5 3 7 1 9

5
1 9 3 7 5
9 3 3 1 7

-1