Bust

ID 38204. Slippers

In my hallway there are 20 slippers in a row – 10 left and 10 right. Coming home, I change my shoes and choose two slippers – left and right, in which it is most convenient for me to stick my legs. Naturally, the left slipper should be to the left of the right one, and the distance (number of other slippers) between them should be as small as possible. Write a program that calculates how many slippers are between the ones I feel most comfortable wearing.

Input
A sequence of 10 zeros and 10 ones is entered, written in some order. The unit corresponds to the left slipper, 0 – right slipper. Numbers are separated by spaces.
Imprint
The program should print the number of slippers between the most comfortable slippers, or -1 if there are none.
 

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 38237. Letters in a circle

Several letters (possibly repeating) are written around the circle. Petya wonders if he will be able to read a certain word if he moves in a circle (in any direction) without missing letters (he can choose where to start and in which direction to move).

Input
The first line contains lowercase Latin letters in the order in which they are arranged in a circle clockwise. Letters are written without spaces, their number is not less than 1 and not more than 100.

The second line contains the word Petya wants to find. It also consists of lowercase Latin letters and has a length from 1 to 100.

Imprint
Print YES in capital Latin letters if such a word can be read moving in a circle, and NO otherwise.

Examples

ID 38239. Preference

In some card game, a deck is used, in which there are 4 aces. 4 players take part in the game, each of which is dealt an equal number of cards, and two cards are put aside.

Each player boasted how many aces he had. Determine how many players knowingly lied.

For example, they said 1, 1, 1, 2. Therefore, 1 player obviously lied. (Some three could tell the truth, but all four could not tell the truth, since there are only 4 aces).

Input
4 numbers are entered (from 0 to 9 each), separated by a space – the number of aces according to the first, second, third and fourth players.

Imprint
Print one number – the minimum number of players who knowingly lied. If everyone could tell the truth at the same time, print the number 0.

Examples

ID 38318. Weighing

Two-pan balances and a set of weights are given. An object weighing K grams is placed on the left side of the scale. Is it possible to bring the scales to a state of equilibrium, and if so, determine for each scale pan which weights need to be placed on it for this. Available weights are allowed to be placed on any of the scales (each weight is available only in one copy, some weights may not be used).

Input
Entered first K — the weight of the item placed on the left bowl (1≤K≤50). Next, the total number of weights N (1≤N≤10) is recorded. Next, N different natural numbers are written, not exceeding 50, — weights.

Imprint
On the first line print the weights of the weights to be placed on the left scale pan, on the second line print — weights to be placed on the right bowl. If no weights need to be placed on some bowl — print the number 0 in this line. If it is impossible to balance the scales with the help of these weights, print the single number –1. If there are several options, print any of them.
 

Examples

ID 38313. Kvass

On a tropical island, kvass is especially popular at the height of the tourist season. Previously, all kvass was imported from Russia, but with the increasing popularity of this drink, the question arose of producing kvass right on the spot. There are N resort towns on the island, all towns are located on the coast. The only ring road on the island runs along the coast, connecting all the cities. Driving on the road is possible in any direction. Each city knows how many barrels of kvass it needs daily.

It is planned to build only one plant in any city, and deliver products to other cities. Transportation of one barrel to a neighboring city costs one tugrik (local currency).

Your task is to determine in which city the factory should be built in order to minimize transport costs.

Input
The first line of the input contains the number N – number of cities (N ≤ 10) and N numbers – the amount of kvass required daily by the 1st, 2nd, …, Nth city (the cities are numbered consecutively along the ring road).

Imprint
Print one number – the number of the city in which the factory should be built. If there are several suitable cities – print the number of any of them.

Examples

#	Input	Output	Explanation
1	3 5 3 10	3
2	6 4 4 1 5 1 3	2	There are 6 cities on the island, the need for each city is indicated in circles, the city number is next to the circle. If you build a plant in the 2nd city (it is grayed out), you will need to pay 4 + 1 (the cost of transportation to the 1st and 3rd cities) + 5*2 + 3*2 (to the 4th and 6th ) + 1*3 (in the 5th, see the picture). In the 2nd we do not carry anything at all. It will be 24 tugriks. It is easy to check that if you build a plant in other cities, the amount will be higher. For example, if you build in the 4th city, then the sum will be 1 + 1 + 3*2 + 4*2 + 4*3 = 28 tugriks.

ID 38334. simple square

Petya has a playing field of 3x3 size, filled with numbers from 1 to 9. At the beginning of the game, he can place a chip in any cell of the field. At each step of the game, it is allowed to move a piece to any cell adjacent to the side, but it is not allowed to visit the same cell twice. Petya carefully keeps the protocol of the game, writing down the numbers in it in the order in which the chip visited the cells. Petya was wondering what is the maximum number he can get in the protocol. Help him answer this question.

Input
The input file contains the description of the — 3 lines of 3 integers separated by spaces. It is guaranteed that all nine numbers are different and lie in the range from 1 to 9.

Imprint
Print a single integer — the maximum number that could result in the protocol when playing on this field.

The answer can be displayed not as a number, but as a string or as a sequence of individual digits (but not separated by spaces).

Examples

ID 38369. Game scheme

In football tactics, one of the basic concepts is the game scheme. It determines how many of the ten outfield players will play defense, how many — in midfield and how much — on the attack.

For example, a 5-3-2 formation means a team has five defenders, three midfielders, and two forwards. In accordance with modern concepts, the following restrictions are imposed on the game scheme: there must be at least one and no more than five defenders, at least one and no more than five midfielders and no more than three attackers. Note that the attackers may not be in the team at all. We will consider only such schemes.

We will assume that the football field has a length of 120 meters and a width of 80 meters. Let us introduce a rectangular Cartesian coordinate system on it in such a way as shown in the figure. The gates of the team we are considering are on the left.

We will also assume that a player is in the midfield line at some point in time if he is at a distance of no more than 20 meters from the center line. Accordingly, the player is in the line of defense if he is no more than 40 meters from "his" the front line, and in the attack line, if it is located no more than 40 meters from the "stranger" front line.


For example, in the situation shown in the figure, there are four players in the defensive line, in the midfield line — three, in the line of attack — also three.

During the game, some players can move from one line to another. In this problem, we assume that it is possible to move from midfield to defense (and vice versa) and from midfield to attack (and vice versa). Thus, a player who, in accordance with the scheme of the game, is a defender, cannot be in the offensive line, and vice versa — a player who, according to the scheme of the game, is an attacker, cannot be in the defensive line. In addition, in accordance with the instructions of the coach, no more than two players could move from each line to each.

Your task is to write a program that, given the positions of the players at some point in time, will find all possible game schemes under which such an arrangement of players could arise during the game.

Input
The input file contains ten lines containing two integers x_i and y_i each, — coordinates of each player on the team (0 ≤ x_i ≤ 120, x_i ≠ 40, x_i ≠ 80, 0 &le ;y_i ≤80).

Imprint
In the first line of the output file print k — the number of game formations a team can play. On the next k lines, in any order, print a description of each of these schemes. Follow the data format shown in the example.

Examples

ID 27221. Bovine Genomics #2

ID 27222. Where's Bessie?

ID 39517. triangles

Farmer John wants to create a triangular pasture for his cows.
There are N fence posts in total (3 ≤ N ≤ 100) as distinct (X₁,Y₁)…(X_N, Y_N) points on the farm map. He can choose three of them to form the vertices of a triangular pasture, but so that one of the sides is parallel to the x-axis and the other is parallel to the y-axis.

What is the sum of the areas of all possible pastures that a FD can form?

Input
The first line contains N.
Each of the following N lines contains two integers Xi and Yi, each in the interval −10⁴…10⁴ inclusive, describing the position of the post.

Imprint
Since the sum of areas may not be an integer and very large, print the remainder after dividing twice the sum of areas by 10⁹+7.

Examples

4
0 0
0 1
10
1 2

ID 28324. Palindromic Paths

ID 28322. Bessie got even

Farmer John and Besi the cow love to trade math puzzles in their free time. The last puzzle FD gave to Besie was quite difficult and Besie couldn't solve it. Now she wants to give FD a very difficult puzzle.

Besi gives a FD expression  (B+E+S+S+I+E)(G+O+E+S)(M+O+O), containing seven variables B,E, S,I,G,O,M ("O" is a variable, not 0). For each variable, it gives the FD a list of up to 20 integers that this variable can accept. Besi asks the FD to count the number of different ways to assign values ​​to variables so that the calculated expression is an even number.

Input

10
B2
E 5
S7
I 10
O 16
M19
B3
G1
I 9
M2

There are 6 possible options for assigning values ​​to variables:

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53.244
                = (2, 5, 7, 10, 1, 16, 2) -> 35.496
                = (2, 5, 7, 9, 1, 16, 2) -> 34.510
                = (3, 5, 7, 10, 1, 16, 2) -> 36.482
                = (3, 5, 7, 9, 1, 16, 19) -> 53.244
                = (3, 5, 7, 9, 1, 16, 2) -> 35.496

Note that (2,5,7,10,1,16,19) and (3,5,7,9,1,16,19) are treated as different assignments even though they give the same result.

ID 28321. Moocryption

ID 39561. cow alphabet

Little known is the fact that cows have their own alphabet "cowphabet". It consists of the same 26 letters from 'a' to 'z', but in a different order.
To pass the time, Besi mumbles cowphabet over and over again. Farmer John wonders how many times she's muttered it.

Given a string of letters that the FD heard from Besie's muttering, determine the minimum number of times Besie must mutter cowphabet for the FD to hear the given string. The FD doesn't always pay attention to Besie's mutterings, so he may not be able to hear some of the Besie's muttering letters. The string given to you contains only those letters that he heard.

Input
The first input line contains 26 small Latin letters from 'a' to 'z' in the order they appear in cowphabet. The next line contains a string of small Latin letters that the FD heard. This string has a length between 1 and 1000.
Imprint
Print the minimum number of times that Bessy muttered the alphabet.

Examples

abcdefghijklmnopqrstuvwxyz
mood

ID 39570. photography of cows

Farmer John wants to take a picture of his grazing cows so he can hang it on his wall. The pasture is represented by a grid of N * N cells (like an NxN chessboard) (2≤N≤1000). The FD wants the cows to be distributed around the pasture with the following rules:
No two cows can be in the same cell.
Each sublattice of size 2×2 (total such sublattices are (N−1)×(N−1)) must contain exactly 2 cows
For example, this placement complies with the rules:

CCC
...
CCC
And such accommodation - no

C.C
.C.
C..
because the 2×2 region in the lower right contains only one cow.
There are no other restrictions. You can assume that the FD has an infinite number of cows.

Some cells are more preferable for PD than others. In particular, the FD considers. that if a cow is placed in a cell (i,j), the beauty of the photo is increased by a_ij (0≤a_ij≤1000) units.

Determine the maximum possible beauty of the correct placement of cows.

Input
The first line contains the number N. Each of the next N lines contains N integers. The j-th number in the i-th row from the top is the value a_ij.
Imprint
Print one integer - the maximum possible beauty of the resulting photo.

 

Examples

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

ID 39674. Huckleberry Finn and two strings

Huckleberry Finn has two strings s and t of the same length n.
Huckleberry Finn likes strings to have the same prefixes (beginnings), so he can swap two characters in string s to make the common prefix of strings s and t larger.
However, this trick is rather tedious, so Huckleberry Finn will either not do it at all, or will do it exactly once.

Help Huckleberry Finn determine the longest common prefix length of strings s and t that he can get.


Input:
The first line contains a natural number n (1 <= n <= 200000) - the length of strings s and t
The second line contains a string s, consisting of lowercase Latin letters.
The third line contains a string t consisting of lowercase Latin letters.

Output:
Print one natural number - the maximum length of the common prefix s and t, which can be obtained by exchanging two characters in the string s at most once.

Examples:
 

ID 39675. cultural contact

At the beginning of the 18th century, a group of European explorers arrived on an island inhabited by a group of tribes that had never come into contact with representatives of European civilization.

To successfully establish contacts with the natives, the leader of the group plans to give a gift to the leader of each tribe he meets. To this end, he brought a long chain of glass, similar to precious stones. 
Let's represent the string as a string s, consisting of small letters of the English alphabet, where each letter means the type of piece of glass at the corresponding position. 
The researchers are going to cut the chain into some fragments, and then hand over exactly one fragment to the leader of each tribe encountered by the group. The research leader decided to split the chain into fragments according to the following rules:

• In order not to spend a lot of time on cutting, each fragment should be a group of adjacent pieces of glass in the chain, that is, a substring of the string s.
• All pieces of glass must be used, that is, each piece of glass must be included in exactly one fragment.
• Because the researchers don't know how the aborigines will value certain types of glass, they want each chief to get the same set of glass without regard to order. In other words, for any type of glass, the number of glass of this type must be the same in each of the fragments.
• Researchers don't know how many tribes live on the island, so the number of prepared fragments should be as large as possible.

ID 39836. Xor paths in a matrix

A rectangular field of size n*m is specified. Each cell contains a non-negative integer. You need to count the number of paths from cell (1,1) to cell (n,m) that satisfy the following conditions.
1) From each cell, you can only move down or right without leaving the field.
2) The bitwise exclusive OR of all numbers on the path must be equal to k.
Find the number of matching paths for the given field.

Input
The first line contains three integers n, m and k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - the height and width of the field, and the number k.
The following n lines each contain m integers ai,j, where j -th element of i-th row is equal to ai,j (0 <= a_i,j < ;= 10¹⁸).

Imprint
Print one integer - the number of paths that satisfy all conditions.
 

Examples

ID 24733. orders

Blaze sends movement orders to his troops, gathered from the inhabitants of one of the shadows. Unfortunately, they don't understand Amber, so Blaze has to send them messages in their own language.
Therein lies the problem: the Amberian prince does not know the spelling of this language well, so he sometimes makes mistakes in words, but no more than one mistake in a word.
There are a lot of words in the language, so if at least one letter in a word changes, then its meaning can change dramatically. If the army does not correctly understand the order, then the entire military campaign may fail. Therefore, it is very important for Blaise to check the correct spelling of words. He decided to ask you to help him.
You must create a program that will output in lexicographic order all the possible words that Blaise could have tried to write, given that he could have made a mistake 1 time.
 

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 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