Problem A. Absolutely simple ≡

Statement

Vasya likes to decrease numbers, but does not like negative numbers. So, he picks some integer A₁ and starts to decrease it by 100 and take an absolute value of the result. In other words, on each step he calculates next number in the sequence A_i + 1 = |A_i − 100|.

When Vasya calculates a number which was already present in the sequence, he gets bored and stops. Your program must, given A₁, determine the number of steps Vasya would perform.

For example, if A₁ = 1 then A₂ = |1 − 100| = 99, and A₃ = |99 − 100| = 1, so Vasya performs 2 steps.

Input file format

Input file contains a single integer A₁.

Output file format

Output file must contain a single integer N — number of steps.

Constraints

0 ≤ |A₁| ≤ 10⁹

Sample tests

1

2

-1

4

500

6

Problem B. Breaking digits ≡

Statement

Given an integer number A in decimal notation, your program must divide its digits between two integers B and C so that:

1. Every digit of A is encountered exactly once in either B or C.
2. The sum B + C is maximum possible.

Input file format

Input file contains a single integer A.

Output file format

Output file must contain two integers B and C. If there is more than one solution, output any of them.

Constraints

10 ≤ A ≤ 10⁹

Sample tests

11

1
1

439

94
3

1000

100
0

Problem C. Carriage inspectors ≡

Statement

Programmer Vasya commutes to work by train every day. Vasya came to the train station today as usual, but forgot his wallet! There is no time to get back. Vasya decided to take the train without buying a ticket. Obviously, he wouldn't be happy to meet an inspector now.

The train consists of N carriages served by M inspectors. Luckily, Vasya always takes this train and knows A_i — numbers of carriages where inspectors are located at the moment he enters the train. He also knows the direction (toward the first or toward the last carriage) of each inspector and his (or her) speed V_i — the number of carriages that the inspector passes per hour. Thus every 1 / V_i hours the inspector moves to the next carriage in his (or her) direction. The inspector stops if there is no next carriage in that direction.

The trip to work is long, so Vasya wants to pick a carriage where he could stay as long as possible until the moment when an inspector shows up in his carriage. Help Vasya with this.

Input file format

First string of the input contains integers N and M — the number of carriages and the number of inspectors accordingly.

Then M lines follow, i-th line contains integers A_i, V_i — carriage number where the inspector i is located when Vasya gets on the train, and his (or her) speed. V_i is negative if the inspector is moving toward the first carriage, and positive otherwise.

Output file format

Output the number of carriage which Vasya should get in to. Carriages are numbered from 1. If there are multiple solutions, output any of them.

Constraints

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

 − 10⁶ ≤ V_i ≤ 10⁶, V_i ≠ 0

Note on samples

In the first sample input Vasya can stay in the carriage number 1 as long as he wants.

In the seconds sample input there are inspectors in carriages 1 and 5 at time 0. After 0.5 hours inspector 1 enters carriage 4. After 1 hour from the beginning of the ride, inspector 1 enters carriage 2, while inspector 2 enters carriage 3. Thus, both 2 and 3 are correct answers.

Sample tests

3 1
2 1

1

5 2
5 -2
1 1

2

Problem D. Dreaming on a train ≡

Statement

Young programmer Vasya goes to work and from work on the train every day.

When returning from work, Vasya is very tired, so he can fall asleep in the train.

On the route from work to Vasya's home there are N stations. Each of them is announced on the radio at the moment when the train is at the previous station. Vasya's station is announced on the N-th station.

If Vasya hears the name of his station, then he will not miss it for sure.

However, every time Vasya listens to the names of the stations, he can fall asleep with a probability of 0.5. In this case, he won't hear the announcement on the next M stations. After sleeping through the announcement of the station, Vasya would never get off the train on it.

Now Vasya thinks whether to give up such a habit of sleeping on the train. For this, he wants to calculate the probability of oversleeping the announcement of his station.

Input file format

The first line of the input file contains integers N, M — total the number of stations and the number of stations that Vasya will sleep.

Output file format

Output a single number — the probability to oversleep the announcement of the station with an accuracy of at least 5 digits after the decimal point.

Constraints

1 ≤ M ≤ N ≤ 1000

Sample tests

2 1

0.5

3 1

0.25

Problem E. Edge of the knight ≡

Statement

In a chess, it is useful in some positions if two knight figures cover one another.

Sergey has already placed one knight on an empty chess board. Now he wants to know number of squares where he can place the second knight so that knights would cover each other.

Input file format

First line contains position of the first knight in a format of HW, where H — column (file), W — row (rank).

Output file format

Output a single integer — number of squares for the second knight.

Constraints

H ∈ (a, b, c, d, e, f, g, h)

1 ≤ W ≤ 8

Note on samples

Remember that a knight moves in a shape of letter L. Knight moves for 1 square in one direction (vertically or horizontally), and for 2 squares in another direction.

In the first sample the second knight can be placed on squares c1, g1, c3, g3, d4 and f4.

Sample tests

e2

6

f5

8

Problem F. Flasks equalizing ≡

Statement

In the laboratory there is a weird construction consisting of N equal cylindrical flasks in a row.

Flask number i contains a_i milliliters of a liquid.

In a single step, you can pour any amount of liquid from a single flask to one or both its neighbours on the left and on the right in any proportion. The amount of liquid in each flask must remain integer value after each step.

Your program must perform the minimum number of aforementioned steps to make all flasks contain the equal amount of liquid.

Input file format

The first line of the input file contains an integer N.

The second line contains N integers a_i. It is guaranteed that the total amount of liquid is divisible by N.

Output file format

The first line of the output file must contain an integer S — the minimum number of steps.

Each of the following S lines contain three integers I, L, R — the index of the flask starting from 1, the amount of liquid to pour into the flask to the left and the amount of liquid to pour into the flask to the right respectively.

If there are several solutions, output any of them.

Constraints

1 ≤ N ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Sample tests

5
7 7 1 5 5

2
2 0 4
1 0 2

5
7 6 1 5 6

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

Problem G. Gablerd Lettres ≡

Statement

Arocdnicg to rsceearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoatnt tihng is taht the frist and lsat ltteer are in the rghit pcale. The rset can be a toatl mses and you can sitll raed it wouthit pobelrm. Tihs is buseace the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Alexey decided to test whether this property will also hold for integers. He picked an integer number N and now wants to rearrange its digits so that:

• first and last digit stay in their places;
• all other digits change their positions.

Additionally for each position except the first and the last one, digits located in this position before and after rearrangement must be different.

You program must rearrange digits of a given integers according to Alexey's requirements.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — an answer to the problem. If there are several solutions, output any of them.

If there is no solution, output  − 1.

Constraints

1 ≤ N ≤ 10⁹

Sample tests

238965

269385

123

-1

Problem H. Healthy run ≡

Statement

Young programmer Vasya decided to start running every morning to keep himself in a good shape.

Vasya googled how to run properly if you have lead a sedentary lifestyle for too long and found an article where the following technique was offered.

You need to run along a circular track divided into N segments. Length of i-th segment is a_i meters.

One should alternate slow and fast running: on the first, third and following odd segments — with the speed of V m/s, on the second, fourth and following even segments — with the speed of 2V m/s.

Vasya wondered how far he would run in T seconds, given the sequence of segment lengths and the starting speed.

Input file format

The first line of the input file contains integers N, V, T — the number of segments, the initial speed and the time that Vasya will run for.

The second line of the input file contains integers a_i — lengths of the segments along the track. The sum of the lengths of the segments is equal to the length of the track.

Output file format

Output file must contain a single number — the distance that Vasya will run in the specified time with an accuracy of at least 5 digits after the decimal point.

Constraints

1 ≤ N ≤ 10⁴

1 ≤ a_i ≤ 10⁴

1 ≤ V, T ≤ 10⁴

Sample tests

1 2 1
1

2.5

2 10 2
3 7

30.5

Problem I. Inverse breaking digits ≡

Statement

Given an integer number A in decimal notation, your program must split it into integers B and C so that:

1. Every digit of A is encountered exactly once in either B or C.
2. The sum B + C is minimum possible.
3. Integers B and C do not contain leading zeroes.

Input file format

Input file contains a single integer A.

Output file format

Output file must contain two integers B and C. If there is more than one solution, output any of them.

Constraints

10 ≤ A ≤ 10¹⁸

Sample tests

11

1
1

439

34
9

1000

100
0