Problem A. Alice and numbers ≡

Statement

Young programmer Alice does not like integers number K.

Alice wants to know number of integers in range from 1 to N (inclusive) not divisible by K.

Input format

Input contains two integer numbers N and K.

Output format

Output a single integer — number of integers not divisible by K.

Constraints

2 ≤ N ≤ 10⁹

1 ≤ K ≤ 100

Sample tests

5 2

3

4 2

2

Problem B. Blown by the wind ≡

Statement

Young programmer Vasya wants to give Alice a birthday present. To do this, he found a beautiful one-dimensional lawn and in N integer coordinates x_i he installed a_i beautiful stones, to show Alice later.

In the morning, Vasya discovered that due to the strong wind blowing in one direction or another, some stones rolled away in different directions. Now in M integer coordinates y_i there are b_i stones.

However, the relative position of the stones could not change. Thus, if the first stone was at the coordinate x₁, and the second stone was at the coordinate x₂ > x₁, then their coordinates y will satisfy inequality y₂ ≥ y₁. Stones that were at the same x coordinates can move to different y coordinates.

Vasya wants to understand how much the arrangement of the stones has changed, so he asks you to calculate exactly how many stones were left standing in their original positions.

Input format

The first line contains the integer N.

The next N lines contain two integers each, separated by a space — x_i, a_i, in ascending order of x_i.

The next line contains the integer M.

Output format

Output the number of stones that remained in their original positions.

Constraints

1 ≤ N, M ≤ 10⁵

−10⁹ ≤ x_i, y_i ≤ 10⁹

1 ≤ a_i, b_i ≤ 10⁹

Sample tests

3
1 1
2 1
3 1
1
3 3

1

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

2

Problem C. Caterpillar ≡

Statement

A caterpillar of length L crawls over rough terrain. Rough terrain can be represented as a one-dimensional array of N cells with different heights. A cell a_i is called a downhill if a_i > a_i + 1. A cell a_i is called an uphill if a_i < a_i + 1. Initially, the caterpillar occupies the first L cells.

In order to advance one cell, the caterpillar spends 1 second of time. However, if it occupies more downhills than uphills, and the head of the caterpillar is on the downhill, it immediately moves one cell to the right.

Determine after how many seconds the head of the caterpillar reaches the last cell.

Input format

The first line of the input file contains two integers L, N. The second line contains N integers a_i.

Output format

The output must contain one integer — time after which the caterpillar reaches the last cell.

Constraints

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

Sample tests

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4

Problem D. Duel of battleships ≡

Statement

Two sailing battleships fight against each other. Each ship have a length of L meters. The guns on the ships are located every meter and are directed strictly perpendicular to the ship. The first gun is located at a distance of 1 meter from the start of the ship. The power of each gun on the first ship is p₁, and on the second p₂.

The duel of the battleships proceeds as follows: two ships sail towards each other along parallel trajectories, at some point the ship's captain gives the order to open fire and all the guns on board the ship shoot in their direction. Two ships can fire in any order, or simultaneously. Each ship shoots exactly once. If at the moment of firing k guns hit the enemy ship, enemy will take p ⋅ k damage, where p is the current firepower of shooting ship's guns, and the firepower of each enemy gun will decrease by (p ⋅ k)1000.

The captain of the first ship wants to understand what maximum damage his ship can inflict on an enemy ship, provided that the enemy is trying to minimize the damage done to his ship.

Input format

The first line of the input contains three numbers: L, p₁, p₂.

Output format

The output must contain a single number  — the maximum damage that the first ship can cause, with an accuracy of at least two decimal places.

Constraints

1 ≤ L ≤ 10⁹; 1 ≤ p₁, p₂ ≤ 10⁷

Sample tests

4 100 100000

100

10.0 1000.0 112

9989.92

Problem E. strEss ≡

Statement

Petya does not cope well with the pronunciation of English words; he especially struggles with placing stress on correct vowels. Therefore, he decided to download the dictionary of English words with stresses and to write a program for placing stresses in words, based on the dictionary data. The dictionary contains N lines, each line of the dictionary consists of a word and a stressed word, separated by a comma and a space.

The dictionary has a number of features: the word can have a main variant of stress (indicated by the character ') and zero or more additional variants of stress (indicated by the character "). Petya is only interested in the main stress variant. There are also errors in the dictionary, namely: main or additional stress variants can indicate a consonant. When seeing an error, Petya does not trust the dictionary and the program should output a string NO for this word.

The vowels are: a, e, i, o, u, y. The remaining letters are consonants.

Your program should process K words and output each word with the main stress (the stressed letter should be capitalized) or NO, if the stress is not correct in the dictionary or the word is not in the dictionary.

Input format

The first line of the input file contains two integers N K. Following N lines contain a dictionary description. The following K lines contain words to put stresses into.

Constraints

1 ≤ N, K ≤ 500

The sum of the lengths of all lines does not exceed 4 ⋅ 10⁴. All strings contain lowercase Latin letters and the following characters: , ' ". It is guaranteed that each word have exactly one main stress and all characters indicating stresses are strictly after the stressed letters.

Sample tests

5 7
apple, a'pple"
stress, stre'ss
cucumber, cu'cu"mbe"r
phonetics, phonetics'
phonetic, ph"o'netic
stress
cucumber
phonetics
phonetic
apple
strass
sdgfousdhg

strEss
cUcumber
NO
NO
Apple
NO
NO

Problem F. Fixed step ≡

Statement

Let us consider a character sequence S consisting of digits and lowercase Latin letters.

It is required to find a subsequence of S that has maximal length and consists of same character located at positions with a fixed step (that is, on equidistant positions).

If there are several solutions, choose any of them with the maximum step.

Input format

Input contains a single string S.

Output format

Output must contain index of the start position and step. Positions are numbered from zero.

If the subsequence has only one element, step must be zero.

Constraints

0 < |S| ≤ 5000

Sample tests

ababbbabab1b2b2b3baa

1 2

abc123xyz456def789pt

0 0

Problem G. Geometric tomography ≡

Statement

Flatlandian scientists investigate different geometric figures. However, due to limited perception, they can only work with one-dimensional projections of real objects. To simplify their life, they created a device that allows to make snapshots of an interesting to them object from different view sides. For the future research they need to develop a program that could restore two-dimensional figure from given snapshots.

Let us consider some convex polygon nested into rectangle ABCD with sides parallel to the coordinate axes (see picture). Let us designate P_AB, P_BC, P_CD, and P_DA — snapshots represented by sets of vertices of the polygon that can be projected to the corresponding edge of the rectangle. There is also a single selected vertex that is marked on any snapshots that include it.

It is required to restore the coordinates of the vertices of the original polygon from the given set of snapshots with the selected vertex marked on them, where the point A is taken as an origin of coordinates.

Input format

Each line of input describes one of the sets P_AB, P_BC, P_CD, and P_DA, represented in the following format. First comes number N followed by N integers — projections of the vertices to the corresponding edge. Following is the index of the selected vertex in the current set, or −1 if there is no selected vertex in the current set.

Vertices in each separate set are numbered from zero in clockwise order.

Output format

Output must contain coordinates of the vertices of the polygon in clockwise order starting from the selected vertex.

Constraints

It is guaranteed that the polygon is not degenerate (i.e. its area is not zero) and any two its vertices do not coincide.

Number of the vertices of the polygon does not exceed 2 ⋅ 10⁵, their coordinates are in range from 0 to 10⁹.

Sample tests

3 54 146 267 -1
4 50 104 210 263 3
4 267 221 117 54 2
3 263 145 50 0

263 117
145 54
50 146
104 267
210 221

4 9 136 257 257 1
4 24 92 221 240 0
4 257 257 136 9 -1
3 240 175 24 2

24 136
92 257
221 257
240 136
175 9

Problem H. Square-convexity: surface ≡

Statement

We call a three dimensional figure square-convex if every line segment which is parallel to the coordinate axes with both ends belonging to the figure, lies completely in this figure.

You are given an image of a square-convex figure in three projections. You are to calculate the surface area of the figure. If the projections do not uniquely determine the shape of the figure, output the area of a figure with maximum possible volume.

Input format

The input contains three projections of the figure, depicted by ASCII graphics: top view, front and right.

Each projection consists of characters "." (ASCII 46) — designation of voids in the description of a projection, and "#" (ASCII 35) — faces of a square-convex body. Each symbol represents a block with the edge length 1. It is guaranteed that in the description of the projection there are neither rows nor columns consisting entirely of voids. A description of each projection ends with a "-" (ASCII 45) in a separate line.

Output format

The output should contain a single integer: surface area.

Constraints

The width and height of each projection does not exceed 100 characters; the figure volume is not equal to zero.

Sample tests

#
#
#
-
#
#
-
.#.
###
-

18

Problem I. Island cafe ≡

Statement

The young programmer Vasya lives on the island and has a lunch every day in a cafe near his home. As a regular visitor, Vasya wants to participate in the bonus program of this cafe. Before doing this, he wants to assess the benefits that he could have received if he had been using bonuses for the last N days.

On the i-th day, Vasya spent a_i coins for lunch in a cafe. According to the terms of the bonus program, he could either accumulate ⌊ 0.01 ⋅ a_i⌋ of the cost of lunch in the form of bonuses, or pay up to ⌊ 0.5 ⋅ a_i⌋ with the bonuses that he has.

Help Vasya find out what maximum amount of money he could save, using bonuses during those N days.

Input format

The first line contains an integer N  — the number of days.

The second line contains N integers a_i, separated by a space symbol — the number of coins Vasya spent on lunch on the i-th day.

Output format

Output a single integer — the number of coins that Vasya could save using the bonus program.

Constraints

1 ≤ N ≤ 10³

1 ≤ a_i ≤ 10⁴

Sample tests

2
1000 20

10

3
100 1000 1000

11

Problem J. Square-convexity: volume ≡

Statement

We call a three dimensional figure square-convex if every line segment which is parallel to the coordinate axes with both ends belonging to the figure, lies completely in this figure.

You are given an image of a square-convex figure in three projections. You are to calculate the volume of the figure. If the projections do not uniquely determine the shape of the figure, output the maximum possible volume for these projections.

Input format

The input contains three projections of the figure, depicted by ASCII graphics: top view, front and right.

Each projection consists of characters "." (ASCII 46) — designation of voids in the description of a projection, and "#" (ASCII 35) — faces of a square-convex body. Each symbol represents a block with the edge length 1. It is guaranteed that in the description of the projection there are neither rows nor columns consisting entirely of voids. A description of each projection ends with a "-" (ASCII 45) in a separate line.

Output format

The output should contain a single integer: figure volume.

Constraints

The width and height of each projection does not exceed 100 characters; the figure volume is not equal to zero.

Sample tests

#
#
#
-
#
#
-
.#.
###
-

4

##
##
-
##
##
-
##
##
-

8