One-Dimensional Arrays

ID 29448. Rose of Wind

When choosing a construction site for a residential complex at a metallurgical plant, it is necessary to take into account the "wind rose"; (the residential complex should be located so that the frequency of the wind from the side of the metallurgical plant would be minimal). To do this, during the year, the wind direction was recorded in the construction area. The data is presented as an array in which the wind direction of the wind for each day (365) is encoded as follows: 
1 - northern (N),
2 - southern (S)
3 - east (E)
4 - western (W)
5 - northwest (NW)
6 - northeast (NE)
7 - southwest (SW)
8 - southeast (SE).
Determine how the residential complex should be located in relation to the plant

Input: 
The first line contains 365 values ​​from 1 to 8 (wind direction)

Imprint:
Print the corresponding letters (abbreviation - see the list above) on which side the residential complex should be built
 

ID 7147. Athlete score

In some types of sports (for example, in figure skating), the performance of each athlete is independently evaluated by eight judges, then the highest and lowest are removed from the entire set of ratings, and the arithmetic mean is calculated for the remaining ratings, which goes to the athlete. If the highest mark was given by several judges, then only one such mark is removed from the set of marks; the same goes for the lowest scores.

ID 7142. The thickest book

The array stores information about the number of pages in each of the 100 books. All pages are the same thickness. Determine the number of pages in the thickest book.

Input
The input is a string containing 100 natural numbers separated by a space. Each number is not greater than 500.

Imprint
Output the answer to the problem.

ID 6004. Filling an array

The first line contains a non-negative number N, the number of array elements (N<=100)
The second line contains two numbers: number A - the value of the first element of the array, number p - the difference between the next and previous element of the array (arithmetic progression)
Fill the array with the elements of the given progression and display it on the screen

Sample input and output

ID 6005. Array filling - 3

The first line contains a non-negative number N - the number of array elements (1<=N<=100)
The second line contains two numbers: the number A is the value of the first element of the array, the number p is the quotient of dividing the current element of the array by the next one (geometric progression) - p>0
Array elements are fractional numbers
Fill the array with the elements of this progression and display it on the screen (all elements are displayed on the screen with an accuracy of up to 6 decimal places)

PLEASE NOTE: The task must use an array, and not just display numbers on the screen. The task will be checked manually after automatic checking!

Sample input and output

ID 6012. Array filling - 2

The first line contains a non-negative number N, the number of array elements (N<=100). 
The second line contains the number b

Fill the array with elements equal to the quotient of the array element index divided by the number b. Array elements are fractional numbers

ID 34987. Yonglings

For training in the Jedi Order, they took very young, Force-sensitive children. But there were also exceptions. At this stage of their training, they were called "younglings". One Jedi works with a group of younglings, but when they move to the rank of Padawans, one Jedi Master is attached to them, individually.

In high jump training, five best younglings are selected for evaluation. Each youngling puts a mark from 1 to 20, after which one lowest and one highest mark is discarded.
You need to write a program that will display the results of the jump.

It should display the five grades given by the younglings without changing their order, and then their sum, while parenthesizing those grades that are not taken into account when calculating the sum.

Examples

ID 34985. Jedi Knights

Error

ID 34986. Impulse of force

Jedi use the Force in their actions. It is described as an energy field that all living beings create that binds together everything in the galaxy. In fact, this is an analogue of the Chinese concept of qi. The Force also has a scientific basis: in the process of "cellular respiration"; chemical reactions occur that generate an electrical impulse, albeit a microscopic one.
The energy impulse can be measured by a number from 1 to 9. Each Jedi, depending on his strength and experience, has his own energy impulse. Anakin Skywalker decided to count how many Jedi with a certain energy pulse.
Write a program that automates this calculation.

Input
The input of the program will be a sequence of numbers ending in zero (all numbers are entered in one line, separated by a space). A maximum of 100,000 numbers will be entered in total.

Imprint
Count the number of 1s, the number of 2s, the number of 3s, and so on in the input sequence. and return the result. The output should always be 9 numbers.
 

Example

ID 34988. flip jumps

A group of younglings are handled by one Jedi, but when they move up to the rank of Padawan, one Jedi Master is attached to them, individually. It was braided behind the right ear, and the rest of the hair was neatly styled.

The Padawan accompanied his master on every dangerous mission in the galaxy. But sometimes the master could leave his student if he thought that this task was too tough for him.

The Padawans lived and trained not only in the temple, but also in special academies and starships.

Padawans also had group training sessions. In group trainings, flip jumps were practiced. & nbsp; The meaning of the training was as follows: it was necessary to turn over in a jump and change your position in such a way that the line of all the Padawans lined up in the reverse order.

Let's enumerate all Padawans in the line with natural numbers 1, 2, 3, ..., N (\(1 <= N < ;= 1000\)).
Write a program that will determine the final position of the Padawans after two flip jumps. First, flip jumps are made from padawan number A to padawan number B, and then from C to  D (\(A<B\); \(C < D\); \(1 <= A, B, C, D <= N\)).

Examples

ID 34990. Strength Gain

"May the Force be with you" — a famous phrase that even those who are not interested in the Star Wars universe have probably heard. 
The ability of an individual to control the Force directly depends on the level of midi-chlorians in his body.

Let us know the strength of each of the N Jedi: A1,...,AN.
Let's designate the maximum and minimum force values ​​as max(A) and min(A), respectively.
Calculate the total strength of all Jedi S, S=A1+A2+…+AN.
Let's replace the power of each Jedi with the difference S and this element: Ai:=S-Ai, \( 1<=i<=N\).
We will call this transformation Increment of force.

Write a program that, given an array B, resulting K–multiply Increment strength to some list of Jedi strengths, calculates the difference max( A)-min(A).

Input 
The first line contains integers N and K, where N — number of array elements B (\(2 <= N <= 10000\)), a K — nbsp;nbsp;number of times Increment Force to initial array A, \(1 <= K <= 100\). 
The second line contains N array elements B. Array elements B — integers belonging to the range from -2 000 000 000 to 2 000 000 000.

Output 

The only line of the output file must contain an integer - the difference between max(A) and min(A).

Example

ID 34989. Bowling alley

Do you want to become a Jedi? Then we give you the code of peacekeeping knights:
No excitement — there is peace
No ignorance — have knowledge
No passion — there is serenity
No chaos — there is harmony
No death — there is Power

N pins are placed in one row, numbered from left to right with numbers from 1 to N. Then, K balls are thrown along this row, while the ith ball knocks down all pins with numbers from li up to ri inclusive.
Your task is to determine which skittles are left standing.

Example

ID 37035. Let's rotate the array

Given a square array. Rotate it 90 degrees clockwise. Write the result to the same array, you cannot use an auxiliary array.

Input
One number n is entered - the size of the square array (n <=10), and then the array itself with the size nхn.

Imprint
Output the resulting array.
 

Example

ID 38188. Symmetric sequence

A sequence of numbers is said to be symmetrical if it reads the same from left to right as from right to left. For example, the following sequences are symmetrical:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Your program will be given a sequence of numbers. It is required to determine what is the minimum number and what numbers must be added to the end of this sequence so that it becomes symmetrical.

Input
First enter the number N — the number of elements of the original sequence (1 ≤ N ≤ 100). Next come N numbers — elements of this sequence, natural numbers from 1 to 9.

Imprint
First print the number M — the minimum number of elements to add to the sequence, followed by M numbers (each — from 1 to 9) — numbers to add to the sequence.

Examples

ID 38210. alarm clocks

The alarm clock on a cell phone can be set to ring at the same time every day, or at a specified time on a specific day of the week. Multiple alarms can be set independently.

Use the information about alarms and the current time and day of the week to determine when the next alarm will sound.

Input
The first line contains three numbers that specify the current time: the day of the week (from 1 to 7), hours and minutes.

The second line contains one natural number N, not exceeding 100 – number of alarms.

The next N lines contain descriptions of N alarm clocks. The description of each alarm consists of three numbers: day of the week (a number from 1 to 7 for Monday,  …, Sunday, respectively, 0 – if the alarm should ring every day), hours (from 0 to 23), minutes (from 0 to 59).


Imprint
Print  separated by a space, three numbers specifying the day of the week, hours and minutes when the next alarm clock rings.
 

Examples

ID 38221. ski jumping

In ski jumping competitions, jumping technique is judged by five judges. Each judge gives a score from 1 to 20, after which one lowest and one highest score is discarded. You need to write a program that will display the results of the jump for a TV broadcast.

It should display the five scores given by the judges without changing their order, and then their sum, and at the same time take into brackets those marks that are not taken into account when calculating the sum

Input
The input is 5 natural numbers from 1 to 20, separated by a space.

Imprint
Print the same numbers in the same order, putting in brackets the minimum (and if there are several – the leftmost of them) and the maximum (and if there are several – the rightmost of them) number, as well as the sum of all numbers not taken in brackets. All numbers (including the sum) must be printed on one line and separated by one space (there must be no spaces inside the brackets). The amount must be preceded by an equals sign, separated on the left and right by a single space. The order of the scores must be the same as in the input.

Examples

ID 38223. gold bars

Given N gold bars. It is required to cut no more than one of them into two parts (not necessarily equal, but with a whole mass), and then divide the ingots into two heaps of equal mass.

Input
The first line contains one natural number N, not exceeding 100.

The second line contains N natural numbers, separated by a space, not exceeding 100 - the mass of the available ingots.

Imprint
Print the masses of the ingots that were included in the first pile (including the mass of the part of the sawn ingot).

If there are several solutions, print any of them.

If there are no solutions, print the phrase NO SOLUTION (in capital letters).

You can display the masses in any order, but the mass of the part of the sawn ingot (if any) should be the last one.

Examples

ID 38242. Sapsan Tickets

Sasha and Lisa — two most ordinary girls who live in Moscow and love St. Petersburg very much. For the holidays, they planned an extensive excursion program in the northern capital, it remains only to buy tickets. The girls know that the fastest way to get to St. Petersburg is on the Sapsan high-speed train. Each car has N rows, each of which has 4 seats, which are numbered like this:

Sasha and Liza have chosen the car in which they plan to travel. It turned out that M tickets have already been sold in this car and it is known which seats are already occupied. The girls decided to buy tickets in this way:

• if there are two places next to each other, then they buy them (for example, 1 and 2 or 3 and 4)
• if there are no two seats nearby, then they try to buy seats next to each other through the aisle (for example, 2 and 4)
• If there are no such seats, then they buy any two free seats.

Examples

ID 38251. Metro

Vanya does not really like people, but, unfortunately, he sometimes still has to take the subway. In such cases, two things help him: headphones with his favorite "Scoprions"; and the right place. Since Vanya wants to be as far away from all people as possible, the right place is considered to be the place from which the distance from the nearest neighbor will be the maximum possible in the car. There are N seats in the car, and they are all located along one wall, and the entrance to the car is at seat number 1. The seats go in a row, without gaps. Vanya understands that sometimes there can be several correct seats, and wants to sit in the correct seat closest to the entrance (that is, the correct seat with the minimum number).

Guess what place Vanya will take in the car.

Input
The first line contains the number N (1 ≤ N ≤ 105). The next line contains N numbers separated by spaces — 0 or 1. The number 0 indicates free space, 1 — busy; places are numbered from left to right. It is guaranteed that at least one place is free.

Imprint
Print the number of the seat where Vanya will sit.

Examples

ID 38254. Cork

One summer day, Arkady and his parents went on a road trip. He really hoped that outside the city they would be able to avoid the hated traffic jams. But, alas, after an hour they got into a traffic jam. Arkady felt sad and thought about how fast they could go if there were no traffic jams ... The section of the road they are on now, — single-lane. And this means that it is not possible to overtake the cars in front. That is, no matter how powerful the car is, it still cannot go faster than the car in front of it. Arkady is well versed in cars and therefore knows the maximum speeds of those cars that are ahead. Now he wants to figure out what the maximum speed each car could be in this area would be.

Input
The first line contains the number N (1 ≤ N ≤ 200) — the number of cars in traffic. The next N lines contain one integer each, and the i-th line contains the speed of the i-th car. The speed of each of the cars does not exceed 300. It is assumed that the (i + 1)-th car goes behind the i-th car, and the first car can go at its maximum speed.

Imprint
Print N numbers — the speed of cars with which they could drive on this section.

Examples

ID 38262. waterfalls

Recently, Uncle Fyodor read in the Murzilka magazine that the highest waterfall in the world — This is the Angel Falls, whose height is 1054 meters. “It would be great to see such a waterfall!”, — he dreamed.

But Venezuela is far away, so for now Uncle Fyodor decided to start by exploring the Smetanka River, which flows next to Prostokvashino. It starts in the hills and gradually descends towards the village. Uncle Fyodor, together with Sharik, walked along the entire course of Smetanka from its source. Sometimes along the way they met waterfalls. As Uncle Fyodor learned from that article in Murzilka, a section of a river with a constant slope angle exceeding 45 degrees, that is, a section whose height is greater than its length, is considered a waterfall.

Already after the trip, over and over again redrawing the map of Smetanka on paper, Uncle Fyodor noticed that if you draw a side view of Smetanka (that is, the higher the point — is drawn, the higher it is above sea level, and the more to the right — the farther it is from the source and closer to Prostokvashino), then we get a non-increasing broken line, which is very easy to analyze. Each segment of this broken line — this is just a section of the river with a constant angle of inclination, which may turn out to be a waterfall!

After spending several evenings studying the Smetanka map, Uncle Fyodor remembered that in addition to waterfalls, there are also cascades of waterfalls. A waterfall cascade is one or more successive waterfalls. Cascade height — is the difference between the heights of the highest and lowest points belonging to this cascade.

Now Uncle Fedor was wondering, what is the height of the highest cascade of waterfalls on Smetanka? Help him: according to the description of the river made by Sharik and Uncle Fyodor, find this number.

Input
The first line contains the number n (2<=n<=10⁵ ) — the number of vertices of the broken line describing the Smetanka river. The next n lines contain the coordinates of these points, the i-th line contains numbers x_i and y_i — horizontal distance from the point to the source and the height of the point above sea level (0x_i<=10⁹, y_i<=10< sup>9 ). The points are listed starting from the source of the river, that is, starting from a point whose x-coordinate is zero and whose y-coordinate is — maximum among all points. It is guaranteed that the river flows from top to bottom and from left to right, that is, each next point is neither higher nor to the left of the previous one.

Imprint
Print one integer: the height of the highest cascade of waterfalls on this river. If the river doesn't actually have waterfalls, print 0.

Examples

ID 38277. Mom, I'm a dispatcher!

Maxim grew up, became disillusioned with big science and now works as an air traffic controller. Every day he does a very important and responsible thing: he lands planes.

This process is not as complicated as it might seem at first glance. The airport where Maxim works has only one runway, so planes must take turns landing. Landing takes b minutes. If the plane arrives and the runway is busy, it is sent to make additional circles over the city until it arrives at an airport with a free runway. One round takes f minutes. If the runway is clear, the plane will immediately start landing. If several planes approach an airport with a free runway at the same time, then one of them goes to land, while the others go to make additional circles.

Today, n planes should arrive at the airport, the time of arrival of each of them is known. How long will it take for all planes to land?

Input
The first line contains three integers n, b, f — the number of planes (1≤n≤1000), the time it takes to land and the time it takes to make one circle over the airport (1≤b, f≤10⁹  ). The next line contains n integers t_i — aircraft arrival times, listed in no particular order (0≤t_i≤10⁹ ).

Imprint
Print a single number: the time it takes for all planes to land.
 

Examples

ID 38289. News selection

Igor reads a news feed in his favorite social network, which consists of n successive entries. Each entry in the feed has its own characteristic — the positivity of a_i , given by a natural number. After reading the i-th entry, Igor's mood improves by a_i .

Igor reads the entries in the order in which they are shown, without skipping any of them. The social network application is designed so that after viewing the last entry, Igor moves to the beginning of the feed and sees the first entry. Igor can start viewing the news feed from any of the entries and read any number of entries in a row, not exceeding n .

Igor feels happy if his mood improved by at least p after reading the news. He wants to feel happy by reading as few entries as possible, because he is already late for the Olympiad! Help him decide which post to start watching and the number of posts to watch, or determine that there aren't enough posts in his feed to make him happy.

Input
The first line contains two numbers n and p ( 1 ≤ n ≤ 1000 , 1 ≤ p ≤ 10⁷ ) — the number of entries in the news feed and the amount by which Igor wants to increase his mood.

The second line contains n non-negative integers a i ( 1 ≤ a_i ≤ 10⁴ ) — positivity of entries in the tape. Neighboring numbers are separated by exactly one space.

Imprint
If Igor can become happy, print two numbers — the number of the record k to start browsing, and the number of records c to look at. If there are several possible answers with minimal c, print the one with minimal k.

If there is no solution, print - 1.
 

Examples

ID 38292. Candy selection

Harry Potter's birthday is coming soon! Hermione wants to prepare an unusual gift for him. She wants to give Harry a set of n magic candies. Each candy is characterized by its taste — an integer t_i . The pleasure that Harry will get from a set of sweets — is the sum of the flavors of all the candies in that set. Note that the flavors of the candies, like Harry's pleasure, do not have to be positive.

Hermione has a huge box of sweets that contains exactly one candy flavor t for every integer t from - 10⁹ to 10⁹. Hermione wants to take n chocolates from this box to make Harry's set.

Hermione wants Harry to enjoy the set of sweets given to him, exactly equal to the integer s . Help her choose the right set, or determine that it's not possible.

Input
The first line of the input contains a single integer n ( 1 ≤ n ≤ 100 ) — how many sweets Hermione wants to put in the set. The second line of the input contains a single integer s ( - 10⁹ ≤ s ≤ 10⁹ ) — the pleasure Harry must get from the set.

Imprint
If it is impossible to make the desired set of candies from Hermione's, print « NO ". Otherwise, in the first line print « YES », and in the second line randomly n numbers — candy flavors in the desired set. If there are several correct answers, print any of them.

Examples

ID 38295. I just need help!

Dr. Rita has a hard day at work today and has gone on her lunch break. During this time, a queue of n people lined up at her office! The queue is long, so the room quickly became very stuffy.

For convenience, let's number the patients with natural numbers from 1 to n in the order in which they initially stood in line: the first was the person with number 1, the second — with number 2 , and so on. The last person was number n.

Further, until Rita returned from lunch, the following event occurred t times: someone from the queue became very stuffy. Because of this, he went outside to get some fresh air, and immediately returned back, standing at the end of the line.

The attentive patient Arseniy wrote down the numbers of everyone who went out to breathe, in the order in which this happened. Now Arseniy is interested in the order in which people stand in line. Help him figure it out!

It is known that no one left the queue completely and no one new came. The next person went out to breathe only after the previous person who went out to breathe returned to the end of the queue.

Input
The first line of the input contains two numbers n and t — the number of people in the queue and the number of events that the person went outside to breathe ( 1 ≤ n , t ≤ 100 000 ).

The second line of the input contains t integers a i ( 1 ≤ a_i ≤ n ) — numbers of people who went out to breathe and then stood at the end of the line in the order in which they did it.

Imprint
Print n numbers — people's numbers in order of priority after all permutations.

Note
In the test from the example, the following changes occurred with the queue:

Person number 2 has moved to the end. People order: 1 , 3 , 4 , 2
Person number 3 moved to the end. People order: 1 , 4 , 2 , 3
Person number 1 has moved to the end. People order: 4 , 2 , 3 , 1
Person number 2 has moved to the end. People order: 4 , 3 , 1 , 2
Person number 1 has moved to the end. People order: 4 , 3 , 2 , 1
Order of people in line at the end: 4 , 3 , 2 , 1 .
 

Examples

ID 38298. Need more candy!

Carlson has a set of n candy jars at home. The jars are numbered from 1 to n , the i -th of them contains a i candies. Carlson considers a set of jars to be cute if this set does not contain three jars with different numbers of sweets.

Carlson has an unlimited supply of sweets in his pockets, so he can add any number of candies to any jar. Help him determine the minimum total number of candies he needs to add to make the set of candy jars cute.

Input
The first line of the input contains a natural number n ( 1 ≤ n ≤ 10⁵ ) — number of cans in Carlson's set.

The second line of the input contains n integers a i ( 0 ≤ a_i ≤ 10⁹ ) — number of candies in jars. Neighboring numbers are separated from each other by one space.

Imprint
Print one number — the minimum total amount of candy that Carlson needs to add in order for the jar set to be cute.

Note
In the first test from the example, Carlson can add two candies to the first jar, and — one candy. Then in the first and fourth jars there will be 7 candies each, and in the second and third — 2 sweets each.

In the second test from the example, the set of jars is initially cute, no candy is required.

Examples

ID 38306. benches

The benches in the park are arranged as follows. Several identical cubic granite blocks are placed in a row, and a granite slab is placed on them (see figure). The modernist architect decided that it would be more interesting if all the shops had different (and not necessarily symmetrical) arrangements of granite foot blocks. At the same time, they are arranged so that the slab does not fall: for this it is enough that there is at least one granite block or part of it both to the left and to the right of the center of the slab (in particular, if the center of the slab falls in the middle of a block, then to the left and to the right of the center of the slab is part of the block, and the slab does not fall).

The thieves discovered that they could pull out the granite blocks one at a time, located on the edge (both on the left and on the right). They want to pull out as many blocks as possible from under the bench without it falling down (you can't move the remaining blocks). Determine which blocks they should leave.


Input
The first line of the input contains two numbers: L - the length of the bench and K - the number of granite blocks-legs. Both numbers are natural and do not exceed 10,000.

The second line is followed by K different non-negative integers, specifying the position of each leg. The leg position is determined by the distance from the left edge of the slab to the left edge of the leg (the leg is a 1x1x1 cube). The legs are listed from left to right (that is, starting with the leg with the smallest distance to the left edge).

Imprint
It is required to list the legs that the robbers need to leave. For each leg, you need to give out its position, as it is specified in the input data. The legs should be listed from left to right, in the order in which  they appear in the input.
 

Examples

ID 38330. Houses and shops

10 buildings were built in a row on Novy Prospekt. Each building can be either a residential building, or a shop, or an office building.

But it turned out that the residents of some houses on Novy Prospekt had to walk too far to get to the nearest store. To develop a plan for the development of public transport on Novy Prospekt, the mayor of the city asked you to find out what is the greatest distance residents of Novy Prospekt have to travel to get from their homes to the nearest store.

Input
The program receives ten numbers as input, separated by spaces. Each number specifies the type of building on Novy Prospekt: ​​number 1 indicates a residential building, number 2 indicates a store, number 0 indicates an office building. It is guaranteed that there is at least one residential building and at least one shop on Novy Prospekt.

Imprint
Print a single integer: the maximum distance from the house to the nearest store. The distance between two neighboring houses is considered equal to 1 (that is, if two houses are side by side, then the distance between them is 1, if there is another house between two houses, then the distance between them is 2, etc.)

Examples

ID 38339. Pancakes

We all know that the winter that has begun will end soon, and everyone will eat pancakes during the Maslenitsa celebration. This will be our task.

N guests are seated at a table, and each has a plate of pancakes in front of them. There are ai pancakes on the plate of the i-th guest. Each guest eats one pancake in one minute, so the time when the last person finishes eating pancakes is equal to the largest value of ai.

Suddenly, another person joined them, and now all those present can shift some of their pancakes (including they can shift all their pancakes, or they may not shift a single pancake) to the newly arrived person. Pancakes are shifted simultaneously and instantly.

The guests want to shift the pancakes in such a way that after shifting they will eat all the pancakes in the minimum time (which is equal to the largest number of pancakes on the guests' plates, including the new guest). Determine the shortest time in which guests can eat their pancakes after being moved.

The program receives as input a natural number N, not exceeding 100.000, – initial number of guests. The next N lines contain natural numbers a_i – the number of pancakes on the plate of the i-th person. The values ​​a_i are given in non-decreasing order, i.e. a_i ≤ a_i+1. The sum of the values ​​of all a_i does not exceed 2·10⁹.

The program should output a single integer – the minimum time for all guests to finish eating their pancakes after transferring some of the pancakes to the new guest's plate.

Examples

ID 38363. Ka-pants

As you know, pants usually consist of two legs. However, the dog needs, for example, pants of 5 legs (for 4 paws and a tail), and the centipede – pants with 40 legs.

Petya has a Beast with M paws. Sometimes – when it is especially cold outside, in order for the Beast not to catch a cold, it may be necessary to put on several pants so that several trousers are worn on each paw.

Petya's mother left N pants for Petya, having respectively K₁, K₂, …, K_N pants, punishing him to put them all on the Beast . Petya wants to put pants on the Beast so that on the most "insulated" the paw turned out to have as few trousers as possible, but at the same time all the trousers left by the mother were put on the beast. Any pants can be worn on any set of paws (each paw can be found only once in a set).

Help him – Write a program that, for each pair of pants, tells which legs their pants should be on. Please note that two legs of the same pants cannot be worn on the same foot (while legs of different pants can be worn on the same foot).

Input
The number M is entered first, and then the number N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Next, N numbers K_i are entered, denoting the number of pants of the pants left by the mother (1 ≤ K_i ≤ M).

Imprint
Print N lines, the i-th line should contain Ki different numbers denoting the numbers of the Beast's paws on which the legs of the i-th pants should be put on. The paws of the Beast are numbered with natural numbers from 1 to M. If there are several required answers, print any of them.

Examples

ID 38364. Turtles

The following problem for younger students is widely known. Three turtles crawl along the road. One turtle says, "There are two turtles ahead of me." The other turtle says, "There are two turtles behind me." The third turtle says, "There are two turtles in front of me and two turtles behind me." How can this be? Answer: the third turtle is lying!

N turtles move one after another along the road. Each turtle says a phrase like: “In front of me are a_i turtles, and behind me are b_i turtles”. Your task is to determine the largest number of turtles that can tell the truth.

Input
The first line contains an integer N (1 ≤ N ≤ 10000) . Then N lines follow, containing integers ai and bi, modulo not exceeding 10000, describing the statement of the i-th turtle.

The data on turtle statements are given in random order, that is, the first statement does not necessarily correspond to the turtle walking at the head of the column, the second - not necessarily following it, and so on

Imprint
Print an integer M – the maximum number of turtles that can tell the truth.
 

Examples

ID 38529.

ID 38505. Candies and boxes

N boxes are arranged in a row. Initially, the ith box on the left contains ai candies.  Gromozeka chooses a box containing at least one candy, and eats one of the candies in the selected box. He can perform this action any number of times. His goal is to ensure that any two adjacent boxes contain no more than x candies.
Find the minimum number of operations required to achieve Gromozeka's goal.

Input
The first line contains two numbers N (\(2<=N<=10^5\)) and x  ;(\(0<=x<=10^9\)).  The second line contains N integers ai (\(0<=a_i<= 10^9\)).

Imprint
Output the answer to the problem.

Examples

ID 38582. The set with the maximum average sum

Given a set of N elements. The value of the ith element (\(1<=i<=N\)) is vi. From this set, at least A and no more than B elements are selected. Find the maximum possible arithmetic mean of the values ​​of the selected elements. In addition, find the number of ways to select elements so that the average value of the selected elements is maximum.

Input
The first line contains three space-separated integers: N (\(1<=N<=50\)), A and B (\(1<=A,B<=N\)). The following N lines contain integers vi (\(1<=v_i< =10^{15}\)), one number per line.

Imprint
Output two lines.
The first line should contain the maximum possible arithmetic mean of the values ​​of the selected elements. The conclusion should be considered correct if the absolute or relative error does not exceed \(10^{-6}\). 
The second line should contain the number of ways to select elements so that the average value of the selected elements is maximum.
 

Examples

ID 21991. Rotate Right

Given an array of N elements (N<=100) 
Write a program that performs a right cyclic shift of even-numbered elements (element numbering starts from 0)

Input
On the first line, enter the value N. Next, on the second line, enter N numbers

Imprint
Output all elements of the converted array.

 

Examples

5
1 2 3 4 5

5 2 1 4 3

ID 33721. Select by divisors

Given an array of numbers. It is necessary to write to another array all three-digit numbers of the original list that are divisible by K and are not divisible by M .

Input
The first line contains the number of numbers  - N . The second line contains space-separated N numbers – array elements (positive integers no more than 10⁵). It is guaranteed that 0 < N <= 10000 . The third line contains two numbers separated by a space – K (1 < K <= N) and M (1 <= M <= N< /code>).

Imprint
The program should display all the elements of the new array in one line, separating them with spaces. If there were no suitable elements in the array, the program should print the number 0.
 

Examples

ID 33202. Использование сортировки 2

ID 1875. Error

Given an array of N elements (2<=N<=15). Remove from it all elements ending in 0

Input format:
At the input are given in the first line N - the number of elements of the array
The second line contains N numbers - the values ​​of the array elements

Output data format: Output the resulting array to a string

Example:
Input
5
43  -50  76  -84 100 

Conclusion
43  76 -84

ID 38692. On the odd side

The number of inhabitants living in each house of the street is known. Houses are numbered in a row, starting from 1. Houses with odd numbers are located on one side of the street, with even ones on the other. Determine how many people live on the odd side of the street.

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (each number is not over 1000).

Imprint
Print a single number - the number of people who live on the odd side of the street.
 

Examples

ID 6009. Error

Given a non-negative number N (0<N<=999999)

Fill the array with its digits in reverse order (the first element is equal to the last digit, the second - the penultimate one, etc.). 

Sample Input and Output

ID 7148. Error

ID 38606. Pair with the same signs

Given an array of integers. Write a program that determines if an array has a pair of adjacent elements with the same signs.

Input
First, the number N — the number of elements in the array (1 ≤ N ≤ 10000). Then N non-zero numbers are written separated by a space - the elements of the array. The array consists of integers.

Imprint
Output the word YES if there is a pair of neighboring elements with the same signs. Otherwise, output the word NO.

Examples

ID 6000. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with elements according to the following rule and display it on the screen in one line separated by a space:

ID 10385. Error

Given an array of N elements.  Delete elements at the beginning and end until the sum of the array is a multiple of 5 (first the first, then the last, etc.).

The first line contains the number N (1<=N<=15)  - the number of elements of a one-dimensional array
The second line contains N integers (numbers are entered from the keyboard)

Sample input and output

ID 29441. First with minimum premium

The array stores information about the annual bonus for N employees of the company. Determine the sequence number of the first employee with the lowest annual bonus.

Input
The first line contains the number N - the number of employees of the company (0<N<=50). The second line contains the values ​​of bonuses for N employees of the company (N numbers, each number is positive, no more than 10⁵) .

Imprint
Print the number of the first employee with the minimum bonus.
 

Examples

ID 7151. Error

Known points (3, 1 or 0) received by a football team for a number of games in the order they were played. It is known that the team won at least one game and lost at least one game.
What happened before: the first win (3 points) or the first loss (0 points)?
The first line contains the number of games played by the team (not less than 2 and not more than 15).
The second line contains points for each game played.
If the win occurred earlier, then output the word WIN.
If the loss occurred earlier, then output the word LOSE.


 

Examples

4
1 0 1 3

LOSE

ID 7145. Last in the race

The array stores information about the results of 25 athletes (seconds) who participated in the ski race. Determine the result of the athlete who came last to the finish line.

Input
The input is a string containing 25 natural numbers separated by a space. Each number is not greater than 250.

Imprint
Output the answer to the problem.

ID 38695. Even indices

Examples

ID 6006. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill an array of N elements with the first natural five-digit numbers whose sum of digits is a two-digit number

Sample Input and Output

ID 1878. Error

Given an array of N positive elements greater than 1 (2<=N<=100). Insert the value of a before the first maximum element, the value of b after the first maximum element. 

Input format:
At the input are given in the first line N - the number of elements of the array
The second line contains number a and number b
The third line contains N numbers - the values ​​of the array elements

Output data format: Output the resulting array to a string

Example:
Input
5
100 200
43  50  76  84 100 

Conclusion
43 50 76 84 100 100 200

ID 33205. Пятый самый легкий

Известны массы в килограммах N предметов (6<=N<=100). Определить массу предмета, являющегося "пятым из самых легких предметов".

Нельзя использовать встроенную сортировку

Пример
Входные данные

ID 7143. most expensive car

The array stores information about the cost of  each of the 50 brands of passenger cars. Determine how much  the most expensive car costs.

Input
The input is a string containing 50 natural numbers separated by a space. Each number is not greater than 100000.

Imprint
Output the answer to the problem.

ID 7154. Error

ID 29444. Last oldest

The array stores information about the year of birth of each of N people. Determine the sequence number of the last oldest person. 

Input
The first line contains the number N - the number of people (0<N<=50). The second line contains the year of birth of N people (N numbers, each number is positive, not more than 10⁵).< br />
Imprint
Print the number of the last oldest person.
 

Examples

ID 7146. The highest and the lowest

The array stores information about the height of 25 people. Determine how much the height of the tallest person exceeds the height of the shortest.

Input
The input is a string containing 25 natural numbers separated by a space. Each number is not greater than 250.

Imprint
Output the answer to the problem.

ID 38696. Odd output

Examples

ID 6001. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with elements according to the following rule (the first element is equal to the value N) and display it on the screen in one line separated by a space:

ID 7034. On the other side of the street

The number of inhabitants living in each house of the street is known. Houses are numbered in a row, starting from 1. Houses with odd numbers are located on one side of the street, with even numbers on the other. Which side of the street has more residents?

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (each number is not over 100).

Imprint
Display a greater than sign (">") if the odd side has more inhabitants than the even side. Display a less than sign ("<< /code>"), if the number of inhabitants on the odd side is less than on the even side. Otherwise, display the sign equals ("=").
 

Examples

ID 33203. (Зл17.11) Средние в шеренге

Известен рост N человек (N-четное, 2<=N<=100). Определить рост тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по ранжиру (по убыванию роста).

Нельзя использовать встроенную сортировку

Пример
Входные данные

ID 1876. Error

Given an array of N positive elements greater than 1 (2<=N<=100). After each element, insert its minimum divisor greater than 1.

Input format:
At the input are given in the first line N - the number of elements of the array
The second line contains N numbers - the values ​​of the array elements

Output data format: Output the resulting array to a string

Example:
Input
5
43  50  76  84 100 

Conclusion
43 43 50 2 76 2 84 2 100 2

ID 7031. Sum of multiples of a

Input
The first line contains the number N (1<=N<=20) - the number of elements of a one-dimensional array. The second line contains N integers (all modulo numbers are not greater than 100). The third line is an integer a.

Imprint
Output one number - the sum of elements that are multiples of the given number a.
 

Examples

ID 29447. OLD or YOUNG

The age of a group of people in the list is known. Which person is listed first: the oldest or the youngest? If there are several oldest (youngest) ones, then take into account the one who met earlier.

Input
The first line contains the number N - the number of people in the list (1<N<=100). The second line contains N numbers - the age of the people in the list (each number is in the range from 0 to 120).

Imprint
Display the word OLD,  if the oldest person occurs first in the list, otherwise the word YOUNG if the youngest occurs first.
 

Examples

ID 38693. Number of positive

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers not equal to zero (all numbers modulo no more than 100).

Imprint
Print one number - the number of positive elements.
 

Examples

ID 10383. Error

Given an array of N elements.  Remove those elements, all elements less than the previous one

The first line contains the number N (1<=N<=15)  - the number of elements of a one-dimensional array
The second line contains N integers (numbers are entered from the keyboard)

Sample Input and Output

ID 33254. Error

The A array contains n integers. Output the + sign if the number of minimum positive numbers is greater than the maximum number of negative ones. Print the sign - if the number of minimal positive numbers is less than the maximum negative ones. If equal, print the sign =.
If there are no positive (negative) numbers among the numbers, then the number of minimum positive (maximum negative) numbers is considered equal to 0.
 

Input
The first line of the input contains the number n (0 <= n <= 10⁵). The second line contains n integers ai - array elements (-10⁹ <= a i <= 10⁹).

Imprint
Output one character (+, -, =) - the answer to the problem.

 

Examples

ID 5998. Error

Given a non-negative number N - the number of array elements (N<=100)

Fill the array with elements according to the following rule and display it on the screen in one line separated by a space:

ID 29439. First fastest

The array stores information about the maximum speed of each of the N brands of passenger cars. Determine the serial number of the first encountered car with the highest speed.

Input
The first line contains the number N - the number of cars (0<N<=50). The second line contains the speeds of N cars (N numbers, each number is positive, no more than 10⁵).

Imprint
Print the number of the first fastest car.
 

Examples

ID 7152. Error

The array stores information about the maximum speed of each of the 40 brands of passenger cars. Determine the speeds of the two fastest cars.
Display two numbers on the screen in descending order separated by a space.

ID 29442. The last one with the lowest premium

The array stores information about the annual bonus for N employees of the company. Determine the sequence number of the last employee with the lowest annual bonus.

Input
The first line contains the number N - the number of employees of the company (0<N<=50). The second line contains the values ​​of bonuses for N employees of the company (N numbers, each number is positive, no more than 10⁵) .

Imprint
Display the number of the last employee with the minimum bonus.
 

Examples

ID 33206. Сортировка по цифрам числа 1

Дано N двузначных чисел (1<=N<=1000). Необходимо вывести их в порядке увеличения первой цифры. Если первые цифры одинаковы, то вывести их в порядке следования в исходном массиве

Нельзя использовать встроенную сортировку

Пример
Входные данные

ID 6007. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with the first natural four-digit numbers whose sum of even digits is greater than the sum of odd ones

Sample Input and Output

ID 10384. Error

Given an array of N elements.  Remove uneven symmetrical elements.

The first line contains the number N (1<=N<=15)  - the number of elements of a one-dimensional array
The second line contains N integers (numbers are entered from the keyboard)

Sample Input and Output

ID 1874. Inversion between two elements

Given a one-dimensional array of dimension N (2 <= N <= 20). Invert elements that are between the maximum and minimum values ​​(the maximum and minimum values ​​should remain in their places).

Input
The first line contains the number N - the number of array elements. The second line contains the values ​​of the array elements.

Imprint
You need to display the resulting array.

 

Examples

ID 33232. Odd indices

Examples

ID 38691. On the even side

The number of inhabitants living in each house of the street is known. Houses are numbered in a row, starting from 1. Houses with odd numbers are located on one side of the street, with even ones on the other. Determine how many people live on the even side of the street.

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (each number is not over 1000).

Imprint
Print a single number - the number of people who live on the even side of the street.
 

Examples

ID 6010. Error

Given a non-negative number N (0<N<=100000)

Fill the array with all divisors of N in direct order.

Sample Input and Output

ID 29445. First youngest

The array stores information about the year of birth of each of N people. Determine the sequence number of the first youngest person. 

Input
The first line contains the number N - the number of people (0<N<=50). The second line contains the year of birth of N people (N numbers, each number is positive, not more than 10⁵).< br />
Imprint
Print the number of the first youngest person.
 

Examples

ID 7029. The sum of large a

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (all numbers according to modulo no more than 100). The third line is an integer a.

Imprint
Print one number - the sum of the array elements that are greater than the number a.
 

Examples

ID 7035. Elements ending in a

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (numbers are entered from the keyboard).
The third line contains the number a. 

Imprint
Print a single number - number of array elements ending with the number a.
 

Examples

ID 7150. With a difference of 10

The number of each of the 40 classes of the school is known. Is it true that the largest class has 10 more students than the smallest? Display the word YES if the answer to the question is yes, or NO otherwise.

Input
The input line contains 40 integers, each number is not greater than 150.

Imprint
Print YES if the largest class has 10 more students than the smallest class. Otherwise, print NO.

ID 33233. Even output

Examples

ID 24677. Average wheat yield

In the Che region, in each of N districts, it was decided to sow free fields with wheat. After the harvest, all the wheat is taken to the store and counted how much was harvested in each area. Known area planted with wheat (Ai, in hectares) in each district, and the amount harvested in each district (Bi, < /sub>in centners). Write a program that calculates the average wheat yield for each district and for the entire region.

Input
In the first line, enter the value N - the number of districts in the region (1 <= N <= 1000). In the second line, enter N numbers  Ai - area of ​​each district (1 <= A_i <= 10⁹). In the second line , N numbers Bi is entered - the yield of each region (1 <= B_i < = 10⁹).


Imprint
Output in the first line, separated by a space, the average yield for each district, rounded to 6 decimal places. In the second line, output the average yield for the region as a whole, rounded to 6 decimal places.

 

Examples

5
10 20 25 30 35
30 40 50 60 70

3.000000 2.000000 2.000000 2.000000 2.000000
2.083333

ID 38694. Number of negative

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (all numbers according to modulo no more than 100).

Imprint
Print one number - the number of negative elements.
 

Examples

ID 10382. Error

Given an array of N elements.  Remove the longest sequence of zeros
(there are no sequences of the same length).

The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array
The second line contains N integers (numbers are entered from the keyboard)

Sample Input and Output

ID 7030. Sum of even elements

Input
The first line contains the number N (1<=N<=20) - the number of elements of a one-dimensional array. The second line contains N integers (all numbers are not more than 100 modulo).

Imprint
Print one number - the sum of even elements.
 

Examples

ID 5999. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with elements according to the following rule and display it on the screen in one line separated by a space:

ID 7144. cheap candy

The array stores information about the cost of 1 kilogram of 20 types of sweets. Determine how much the cheapest candies cost.

Input
The input is a string containing 20 natural numbers separated by a space. Each number is not greater than 250.

Imprint
Output the answer to the problem.

ID 29440. Last fastest

The array stores information about the maximum speed of each of the N brands of passenger cars. Determine the serial number of the last met car with the highest speed.

Input
The first line contains the number N - the number of cars (0<N<=50). The second line contains the speeds of N cars (N numbers, each number is positive, not more than 10⁵).< br />
Imprint
Print the number of the last met car with the highest speed.
 

Examples

ID 7153. Error

The array stores information about the results of 22 athletes who participated in the 100-meter race. It is known that no two athletes finished at the same time Determine the results of the two athletes who took first and second places (output the answer in a string). 

ID 29443. First oldest

The array stores information about the year of birth of each of N people. Determine the serial number of the first oldest person. 

Input
The first line contains the number N - the number of people (0<N<=50). The second line contains the year of birth of N people (N numbers, each number is positive, not more than 10⁵).< br />
Imprint
Print the number of the first oldest person.
 

Examples

ID 33207. Сортировка по цифрам числа 2

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке увеличения первой цифры в числе. Если первые цифры одинаковы, то вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

ID 38697. Odd on odd

Examples

ID 6008. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with the first natural numbers greater than 300, divisible by 13 or 17 and with a sum of digits greater than 10;

Sample Input and Output

ID 6002. Error

Given a non-negative number N, the number of array elements (N<=100)

Fill the array with elements according to the following rule (the first element is equal to the value N) and display it on the screen in one line separated by a space:

ID 7033. different from the last

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (all numbers are not over 100).

Imprint
Print one number - the number of elements other than the last element.
 

Examples

ID 38698. Odd to even

Examples

ID 38699. Even on odd

Examples

ID 38700. Even on even

Examples

ID 38701. List of Sergei Nikolaevich

Sergey Nikolaevich likes to study statistics. At his disposal came across a list of the growth of all the students of the lyceum. To his chagrin, all the data was written in random order and, moreover, took up several pages. One page contains a record of 25 students. Help Sergey Nikolaevich determine on which page there is information about the first highest and first lowest lyceum students. Pages are numbered from 1.

Input
The first line contains the number N - the number of people in the list (1<N<=10⁵). The second line contains N numbers - growth of people in the list (each number in the range from 100 to 220).

Imprint
Display 2 numbers on the same line separated by a space:
- the first number is the number of the page on which the information about the first highest student is located;
- the second number - number of the page on which the information about the first lowest student is located. 
 

Examples

ID 38702. List of Sergei Nikolaevich - 2

Sergey Nikolaevich likes to study statistics. At his disposal came across a list of the growth of all the students of the lyceum. To his chagrin, all the data was written in random order and, moreover, took up several pages. Having learned the height of the tallest and shortest of the students, Sergei Nikolaevich began to look for these data on the list. It takes 1 millisecond to read one record. Determine how many milliseconds it will take for Sergey Nikolaevich to find records of the highest and lowest students. If there are several such students, Sergey Nikolaevich takes the first one he meets.

Input
The first line contains the number N - the number of people in the list (1<N<=10⁵). The second line contains N numbers - growth of people in the list (each number in the range from 100 to 220).

Imprint
Print a single number on the screen - the number of milliseconds that Sergey Nikolayevich will need to find the required records.
 

Examples

ID 38703. List of Sergei Nikolaevich - 3

Sergey Nikolaevich likes to study statistics. At his disposal came across a list of the growth of all the students of the lyceum. To his chagrin, all the data was written in random order and, moreover, took up several pages. Sergey Nikolaevich wants to determine how many students have the same height as the tallest student, and also how many students have the same height as the shortest student. Sergei Nikolaevich asked you to write a program for him that would solve this problem.

Input
The first line contains the number N - the number of people in the list (1<N<=10⁵). The second line contains N numbers - the age of the people in the list (each number in the range from 100 to 220).

Imprint
Print two numbers on the same line separated by a space: how many students have the same height as the tallest student, and how many students have the same height as the shortest student.
 

Examples

ID 38709. Will we save Libank

Libank International Bank has N branches around the world. After the end of the coronovirus pandemic, the financial department of the bank decided to check the accounts of all branches. It turned out that some branches remained in debt, and some even managed to make a profit. Now the CFOs have decided to bail out all branches with minimal equal debt. They want to see if all their debts can be covered by using the funds of all branches with a minimum equal profit. You, as an employee of the IT department, have been given this task. CFOs are waiting for your response!

Input
The first line contains the number N (2<=N<=500) - the number of branches of Libank. The second line contains N numbers a_i (-1000<=a_i<=1000, 0<=i<N) - positive numbers denote profits of departments, negative - debts. It is known that at least one branch of Libank made a profit and at least one branch remained in debt.

Imprint
If all the specified branches can be salvaged, display the amount that will remain after paying off all the debts of the branches with the minimum equal debt. If it is impossible to save, print a negative number showing how much money is missing.
 

Examples

ID 38715. Sadness Gromozeki

Gromozek has a sequence of integers A of length N. It freely chooses the integer b. Here he will become sad if Ai and b+i are far apart. More precisely, Gromozeka's sadness is calculated as follows:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\) .
Here \(abs(x) \) is a function that returns the absolute value of x. Find Gromozeka's minimum possible sadness.

Input
The first line contains an integer N  (\(1<=N<=2 \cdot 10^5\)). The second line contains N integers Ai (\(1<=A_i<=10 ^9\)).

Imprint
Display Gromozeka's minimum possible sadness.
 

Examples

ID 39382. Will you solve it?

There are N parts of some source code. The characteristics of the ith part of the code are represented by M integers Ai1, Ai2< /sub>, ..., AiM . You are given integers B1, B2, ...< /font>, BM , and C.
The ith part of the code solves the problem correctly if and only if \( A_{i1}\cdot B_1 + A_{i2} \cdot B_2 + ...+ A_{iM}\cdot B_M +C>0\).
Among the N parts of the source code, find the number that correctly solve this problem.

Input
The first line contains three space-separated numbers: N, M (1 <= N, M <= 20) and C (- 100 <= C <= 100). The second line contains   M numbers Bi (-100 <= B_i <= 100). Each of the following N lines contains M numbers Ai (-100 <= A _ij <= 100, 1 <= i <= N, 1 <= j <= M).

Imprint
Print one number - the answer to the problem.
 

Examples

ID 39397. Gromozeka and Alice - 2

Alice and Gromozeka went for a walk around the city. Entering the first cafe, Alice looked at her watch and remembered the time of entry. Further, she memorized only the number of minutes that she and Gromozeka spent between two cafes visited (from entering one cafe to entering another). At the end of the walk, Alice decided to restore the chronology - the time of entering the next cafe.
Write a program that will determine at what time Alice and Gromozeka went to the next cafe. 

Input
The first line specifies the moment of time at which Gromozeka and Alice entered the first cafe. Time format: hours (a number from 00 to 23), followed by a colon, then minutes (a number from 00 to 59). The time string is written without spaces.
The second line contains a natural number N (2 <= N <= 1000) - the number of visited cafes (including the cafe from which they left at the initial moment of time and the last cafe). The third line contains N-1 number: the first one shows the time in minutes from the entrance to the first cafe to the entrance to the second one, the second - the time from the entrance to the second cafe to the entrance to the third one, and so on. Each of these numbers is natural and does not exceed 1000.

Imprint
Print for each cafe the entry time of Alice and Gromozeka. The time format must be the same as in the input data.
 

Examples

ID 39516. Mad scientist

Farmer John ordered N of his cows (1 & le; N & le; 1000), each of which has one of two breeds Holsteins or Guernseys. He fixed this order as a string of N characters, each of which is either H or G respectively. Unfortunately, when the cows arrived at the farm and he lined them up again, they formed a different line from the original.

Let's call these two strings A and B, where A is the original string he wanted to see, B is the string that came out when the cows arrived. FD asked Cousin Ben for help.

After several months of work, Ben has created an amazing MCBF-3000 machine that can take any substring and change all Gs to Hs and all Hs to Gs. A. Help FD.

Input
The first line contains N, and the next two lines contain strings A and B. Each of the strings consists only of characters H and G.
Imprint
Print the minimum number of times the MCBF-3000 machine is used to transform string B into string A.

Examples

7
GHHHGHH
HHGGGHH

ID 42268. Hidden map

In the deck, Gromozeka has cards on which one whole number is written. Each number in the deck occurs exactly 4 times. 
Thus, in the deck there are 4 cards with the number 1, 4 cards with the number 2, ..., 4 cards with the number N. In total, there are 4*N cards in the code.

Gromozeka shuffled those cards, then hid one of them and gave you a stack of the remaining 4*N-1 cards. The i-th card (1<= i <=4*N−1) from the stack contains an integer Ai.

Find the integer written on the card that Gromozeka hid.

Input
The program receives two lines as input. The first line contains the integer N (1 <= N <= 10⁵).  The second line contains 4*N-1 integers Ai (1 <= Ai <= 4*N−1. 1<= i <=4*N−1). For each k (1<=k<=N) there are at most 4 i indices, such that Ai=k.


Imprint
Print the answer to the problem.
 
 

Examples

ID 42271. Number of elements greater than both neighbors

You are given an array of integers. Write a program that in the given array determines the number of elements that have two neighboring elements and, at the same time, both neighboring elements are less than the given one.

First given is a number N - number of elements in the array (1 <= N <= 10000). Then, space-separated  N numbers - elements of the array. The array consists of integers.

You need to output the number of array elements that have two neighbors and are strictly greater than both of their neighbors.

Examples

5
1 2 3 4 5

0

5
2 3 2 4 3

2

ID 42273. Children in a circle

Anna Nikolaevna plays a game with children in kindergarten. There are chairs in a circle. All chairs are numbered from 1 to N (1 <= N <= 100000). Children also have numbers from 1 to N. Initially, each child sits on a chair with the same number. That is, a child with number 1 sits on a stupa with number 1, a child with number 2 sits on a chair with number 2, and so on. Then Anna Nikolaevna claps her hands K times  (|K| <= 100000) quietly or loudly. If Anna Nikolaevna claps her hands quietly, then all children should quickly transfer to K chairs to the right. If Anna Nikolaevna claps loudly, then all children should quickly transfer to K code> chairs to the left. 
To make it easier for Anna Nikolaevna to determine whether all the children moved correctly, write a program for her that would determine the position of each child after transplantation. 

You cannot use additional arrays (lists) in this task. Please note that you need to convert the existing array (list) and print it out as a whole, and not create a new one, even naming it with the same name (this is possible in Python).

The first line is a natural number N, the second line N integers, and the last integer K . All numbers in the input do not exceed 10⁹. If the number K > 0, this means that Anna Nikolaevna clapped her hands quietly. Number K < 0, which means Anna  Nikolaevna clapped her hands loudly.

It is required to display the numbers of children who will occupy chairs from 1 to N after transplantation. 

Examples

5
5 3 7 4 6
3

7 4 6 5 3

ID 42274. ocean view

Mountains stretch from east to west, and the ocean to the west. There is a hotel on top of every mountain. You want to choose which hotel to stay at. The height of the ith mountain from the west is Hi. You can of course see the ocean from the hotel, which is located on top of the westernmost mountain. For a hotel on top of the ith mountain from the west (i = 2, 3, ..., N) you will be able to see the ocean if and only if H1<=Hi, H2<=Hi, ... , and Hi-1<=Hi. Count from how many of these hotels you can see the ocean?

Input
The first line contains a natural number N (1 <= N <= 20) - the number of mountains. The second line contains N numbers Hi (1 <= H_i <= 100) the heights of the mountains, starting from the most western (first).


Imprint
Print the number of hotels where you can see the ocean.
 
 

Examples

4
6 5 6 8

3

5
4 5 3 5 4

3

5
9 5 6 8 4

1

ID 42450. I change candy for a laptop

Anton B., a super bright 8th grade student, has unsurprising math skills. Having once been on an excursion in Kolokolamsk, he realized that he could easily write a program that would predict the cost of his favorite sweets for any period of days ahead. 
Using this program, Anton B. decided  to buy sweets with all his pocket money (and he had only 10 rubles of them), then, a little later, sell all the sweets he bought. Thus, Anton B. wants to earn as much money as possible for a new laptop. 
Since  Anton B. is still a minor and cannot go to other cities alone, he needs to figure out which of the two days to ask his older brother to take him to Kolokolamsk. The older brother is an adult and loves his younger brother very much, so he is always ready to help him.
Since Anton B. is in a hurry for the computer science class, he asks you to determine these two days in the next N days. 

Input
The first line contains the number N (2 <= N <= 100000) the number of days for which Anton B. makes a forecast. The second line contains N  positive integers ai (1 <= i <= N , 1 <= a_i <=  5000 ) , where ai is the predicted cost of candies on the ith day.

Output

Print two numbers: the first number is the number of the day on which Anton B. will go to buy sweets, the second - the number of the day on which he will go to sell sweets. If there are several such variants of days, print any of them. If in the end Anton B. cannot make a profit under any of the options, print two zeros.

6
10 3 5 3 11 9

2 5 

4
5 5 5 5

0 0

ID 42838. five courses

Selena Lunar Restaurant serves the following five dishes:

Nyagao (rice cake): A minutes to serve.
Jiao (dumplings): takes B minutes to serve.
Tang (sweet rice balls): C minutes to serve.
Shiitake (stewed mushrooms): D minutes to serve.
Hanbagu (hamburger patty): takes E minutes to serve.

Let's assume that the time of serving the dish is the time between the placement of the order and the delivery of the dish.

The lunar restaurant has the following ordering policies:

• An order can only be placed at a multiple of 10 minutes (0, 10, 20, ... minutes). 
• Only one dish can be ordered at a time.
• A new order cannot be placed if the dish from the previous order has not yet been delivered. But a new order can be placed exactly at the time when the dish from the previous order has been delivered.

Examples

ID 43349. Secret Sequence

Alice left a secret sequence a[1..n] for her father Professor Seleznev. In order not to hide it, she decided to write it in the most visible place, but in a different order of numbers. Professor Seleznev knows that Alice rewrote the secret sequence as follows:

• the first number on the left is the number a1;
•  the first number on the right is the number a2;
• the second number from the left (after a1) is the number a3;
• the second number from the right (that is, before the number a2) is the number a4;
• all other numbers are written in the same way.

That is, if the secret sequence was a = [1, 2, 3, 4, 5, 6], then the professor would see the following sequence [1, 3, 5 , 6, 4, 2]. Professor Seleznev was in a great hurry and only managed to save the sequence he saw into the computer. Write a program that will show the professor the original secret sequence.

Examples

ID 43517. Autumn Festival

In kindergarten, the Sun for the Autumn Festival, all children should have the same number of balloons. The teacher Anna Nikolaevna found out how many balloons each child can bring from home for the holiday. & nbsp; To equalize the number of balloons for all children, the parent committee decided to purchase the required number of balloons.

In total, in the group of Anna Nikolaevna n pupils, the number of available balloons for each child is ai.< /p>

You are the treasurer of the parent committee, which needs to calculate the minimum number of balloons that must be purchased in order to equalize their number for each child.

We will assume that the balloons that the children have will not burst until the end of the holiday.

Input data

The first line of the input contains an integer n (1 <= n <= 100) — the number of pupils in Anna Nikolaevna's group.

The second line contains n numbers a1,a2< /code>, ..., an, where ai  (0 <= ai <= 106) &mdash ; the number of balloons that the ith child can bring from home.

ID 43532. Books off the shelf

Peter has an extensive library of books. Now he stands near the shelf with adventure stories. It contains n books. All books on Petya's shelf are always numbered from left to right. Book number i has ai pages. On the shelf, next to which Petya is now standing, the number of pages in each book is different.

The peculiarity of the shelves in Petya's library is such that he can only take the last book from the shelf (that is, either the leftmost or the rightmost).

Petya is leaving for the holidays with his grandmother and wants to take two books with him, the thickest and the thinnest. Help Petya find out what is the minimum number of books he needs to remove from the shelf before he gets the two books he needs. Please note that Petya also removes the thickest and thinnest books from the shelf, so they are also considered. 

Input
The first line contains a single integer n (2 <= n <= 100) - the number of books on the shelf.  The second line contains n different integers a1, a2, ..., an (1 <= ai  <= 106) - number of pages in the book.

Imprint
Print a single integer — the minimum number of books Petya needs to remove from the shelf.

Examples

5
1 5 4 3 2

2

8
2 1 3 4 5 6 8 7

4

ID 43533. Lucky Sequence

Peter has a sequence of A non-negative integers of length n. The numbers in the sequence are numbered starting from zero. Peter considers the sequence happy if the parity of each element of the sequence coincides with the parity of the number of the given element. Formally, this means that if for all i (0 <= i <= n - 1) the equality i mod 2 = a[i] mod 2, where x mod 2 is the remainder of dividing x by 2, then the sequence is lucky.

Peter wants to make his sequence happy, for this he takes any two elements and swaps them (the elements are not necessarily adjacent). Help Petya find the minimum number of moves in which he can make his sequence happy. If Petya fails to make the sequence happy, print -1.

The program receives an integer as input in the first line n (1 <= n <= 40) — the size of the sequence A. Followed by a string containing n integers a0,a1 ,…,an−1 (0 <= ai < = 1000) — integer non-negative numbers of the sequence.

For each test case, print one integer — the minimum number of moves required to make the given sequence A happy, or -1 if it is impossible.
 

Examples

4
3 2 7 6

2

1
7

-1

7
4 9 2 1 18 3 0

0

ID 43565. Вывод четных

5
1 2 3 4 5

2 4 

ID 43566. Number equal to last

Input
The first line contains the number N (1<=N<=20)  - the number of elements of a one-dimensional array. The second line contains N integers (all numbers according to modulo no more than 100).

Imprint
Print one number - the number of elements of the source array equal to the last element (the last element is not counted).
 

Examples

ID 44714. Unlucky sea battle

Today, Maxim was unlucky in    "Battleship". Playing with a neighbor on the desk, he never hit a single enemy ship. The game continued until Mar Ivanna saw that the guys were busy in the lesson with the wrong things.  The game had to end ahead of schedule with the victory of the neighbor. Having arrived home, Maxim decided to determine the maximum length of the enemy's ship. 
But now his mother distracted him and called him to dinner. He's gone out to dinner and asked you to help him find the answer. 

Sea battle is a game played on a 10 x 10 checkered field. Maxim managed to send you the field of the last game. On the field, cells are marked that Maxim has already shot. Ships of any size can be placed on the field, but the obligatory condition is that the ship be rectangular with width equal to 1. It is allowed to position the ship either horizontally or vertically.

At input, the program receives 10 lines of 10 numbers each, the numbers are separated by spaces. The number 1 means that the corresponding cell was shot, the number 0 – that they didn't shoot at the cage.
(It is guaranteed that there is at least one unbeaten cell on the field.)

Print the answer  – the maximum possible length of the ship.
 

Examples

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

10

ID 18726. Carousel

Examples