Implementation task

ID 38282. Team Jupiter

Every year in one of the corners of our universe the Intellectual Olympic Games are held. This year, the honor of hosting this large-scale event fell to the planet Jupiter. You have to select two teams for the Games from the available n candidates for the national team.

All candidates are schoolchildren, each candidate studies in a certain class. Like on Earth, Jupiter has 11 classes, numbered from 1 to 11. Two teams are selected for the Games based on the results of the qualifying competitions. There are five qualifying rounds for the competition. At the end of each round, each student can score from 0 to 300 points, the more the better.

The four best schoolchildren get into the first team according to the sum of points scored in all qualifying rounds. The top four in terms of total points from those who did not make it to the first team, and at the same time do not study in grade 11, get into the second team.

All rounds have already been held, and it turned out that any two candidates scored a different number of points in total. It remains only to write a program that, according to the available data on the candidates and the results of the rounds, will determine those eight who will defend the honor of Jupiter at the Intellectual Olympic Games and prove that Jupiter — super planet!

Input
The first line of the input contains a single number n — the number of candidates for the Jupiter team ( 8 ≤ n ≤ 500 ).

The next n lines contain information about the candidates. Each line contains 6 integers — the number of the class in which the next candidate is studying, and his results in the qualifying rounds.

The class number is a number from 1 to 11, and the result on each round — number from 0 to 300.

It is guaranteed that all participants have different total scores.

It is guaranteed that there are at least 8 candidates who are not in grade 11.

Imprint
Output two lines.

The first line must contain four space-separated integers — the numbers of the candidates who will get into Jupiter's first team. Candidates are numbered starting from one in the order they appear in the input. Numbers should be displayed in ascending order.

The second line should describe the second Jupiter command in a similar format.
 

Examples

ID 38623. Cake set

Wushan from the planet Blook opened a bakery. His bakery sells N kinds of cakes. Each type of cake has three parameters: "beauty", "taste" and "popularity". The 1st kind of cake has xi beauty, yi flavor and zi popularity. These values ​​can be zero or negative.
Gromozeka decided that he would buy M pieces of cake. It selects a set like this:
- You cannot use two or more pieces of the same type of cake.
- With the above condition, the set of cakes that maximizes (absolute overall beauty value) + (absolute overall taste value) + (absolute overall popularity value) is selected.
Find the maximum possible value (total beauty absolute value) + (total taste absolute value) + (total popularity absolute value) for the set of cakes Gromozeka chooses.

Input
The first line contains two space-separated integers N (1<=N<=1000) and M (0<=M<=N). The next N lines contain   three integers xi, yi and zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).< br />
Imprint
Print the maximum possible value (absolute value of overall beauty) + (absolute value of overall taste) + (absolute value of overall popularity) for the set of cakes Gromozeka chooses.
 

Examples

ID 38873. Room

The room is characterized by three integers: length, width and height, given in millimeters. A room is considered good if the following conditions are met:
the ratio of the smallest of the length and width to the height is at least 2, as well as the ratio of the largest of the length and width to the smallest does not exceed 2.
Based on the dimensions of the room, determine if it is a good one.

Input
The input is three integers: w, l and h — length, width and height of the room, each
on a separate line (1000 ≤ w, l, h ≤ 10,000).

Imprint
If the room is good, print "good", otherwise print "bad".
 

Examples

ID 39062. broken printer

A broken color printer, printing numbers, paints all enclosed areas red.  For example, the numbers 0, 4, 6, 9 have one closed area.  In the figure 8 - 2 closed areas.  In other numbers, there are no closed areas that are painted over. There are h closed areas remaining in the red printer for painting.  Find the minimum non-negative number that will print out the red ink in the printer. The number must not contain leading zeros.  If the printer is out of red ink, it cannot print a closed area number.

Examples

ID 39388. Contact tracing

Farmer John continues to take care of the health of his cows, consecutively numbered 1…N.
Recently, the FD checked them all and found out that some of them are sick. Using video from the barn, the FD can find out which pairs of cows interacted to spread the disease. The FD has collected a list indicating the time at which the interaction of pairs of cows in the video (t,x,y) took place, meaning that at time t cow x interacted with cow y. The FD also knows the following:

1.  Exactly one cow was initially infected (patient zero).
2.  Once a cow is infected, she passes the infection on to her next K interactions (possibly involving the same partner multiple times). After K times of transmission, she stops transmitting the infection (on realizing that she is infecting, she begins to thoroughly wash her hooves).
3.  Once she gets sick, she stays sick.

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 27222. Where's Bessie?

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 43351. Tommy's books

Tommy loves to read. He took n books from the library (in the ith book ai pages, pages are numbered with < code>1). Tommy is very careful with books, so he wrapped each of them in a cover. But, since he did not have any transparent covers, he numbered the books from 1 to n and wrote the number on the cover of each book.

Tommy has been reading for m days in a row. He reads books strictly in order, starting with book number 1.  Every day, he writes down on the board the total number of pages he has read so far.

For example, if Tommy took 2 books and, at the same time, there were 3 pages in the first book, and 5 pages in the second, then after reading 2 pages on the first day, and 4 pages on the second day, Tommy had on the board two numbers 2 and 6 would be written.

Tommy took a short break, and when he returned to reading, he realized that he had forgotten which book he was reading and which page he had stopped on. He also does not want to lose statistics, but wants to correct it by adding on what day which book he read and on which page he stopped. Help Tommy, by the numbers written on the board, to determine on what day what book he read and on what page he stopped.

Output m lines. In each line print two numbers - нbook number k (1 <= k  <= n) and page number in this book s (1 <= s <= ak) that Tommy settled on for the current day.

Examples

ID 43474. Gromozeka and valerian

Gromozeka loves valerian very much. On his home planet Chumaroza you can buy for k chumriks (local currency) the first package of valerian, for 2·k chumriks -  the second and so on (in other words, ith packing you have to pay i·k chumrikov). Gromozek wants to buy  w packages of valerian.  He has n chumriks. How many chumriks will he have to take on credit from the chumaroz bank in order to buy w packages of valerian?

The first line contains three positive integers k, n, w (1  <=  k, w< /code>  <=  1000, 0 <= n <= 109) , the cost of the first package, Gromozeka's initial number of chumaroziki and the number of packages of valerian he wants to buy.

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 43718. Misha's Cubes

Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has n cubes with letters, in the second - m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number k determine the string that little Misha received.

The string x is lexicographically less than the string y only and only if one of the following conditions is true:
- x is a prefix of y, but x != y;
- in the first position, where x and y differ, in the string x there is a letter that is in the alphabet earlier than the corresponding letter y.


Input
The program receives several lines as input. The first line contains three numbers: n - the number of cubes in the first row, m - the number of cubes in the second row, k > is an integer(1 <= n, m, k <= 100). The second line contains a string a of length n - a string formed by reading the letters written on the cubes of the first row. In the third line - string b of length m - a string formed by reading the letters written on the cubes of the second row.

Imprint
Print the answer to the problem.
 
 

Examples