Strings

ID 33219. Encryption - 2

ID 21533. Line - 4

[:|/||\|:]

ID 21532. Line - 3

\\||//\\||//||\\||//

ID 21530. Line - 2

(:)]-/\-\/

ID 21531. Line - 5

(-["|-|-|"]-)

ID 21529. Line - 1

<@(/\/\)>< 

ID 33533. Treasure

The path to the treasure is set in the form of indications of how many steps you need to go in one of the four directions: north (N), south (S), west (W), east (E). The entire route is written as a string containing a sequence of numbers followed by letters indicating the direction of movement. For example, the string "7N5E2S3E" means "walk 7 paces north, 5 paces east, 2 paces south, 3 paces east". A route can have many move commands, so each such route can be abbreviated.
For example, the previously given route can be shortened to "5N8E". For the given route to the treasure, shorten it to a string of minimum length.

The program receives as input a string consisting of non-negative integers, not exceeding 10⁷ each, and one letter (N, S, W, E ) following each
number. There are no other characters (including spaces) in the string except numbers and direction letters. The string length does not exceed 250 characters. It is guaranteed that the initial
and the end point of the route are different.
The program should output a route leading to the same point, written in the same form as in the input, using the minimum number of characters. If answers
several, the program should display one (any) of them.
 

ID 21537. Arrow

(
   \
     )
##-------->
     )
   /
(

ID 21535. gnome

  /_\
{~._.~}
 ( Y )
()~*~()
(/)-(\)

ID 21538. flower

 0 0
0" 0
 0 0
    \/\
     \/

ID 21536. Dog

_ _ ;;
.~.~~;;;;;;;
\_/-\|----\\
 ' "" ""

ID 23385. Increase numbers - 1

The first line of input data contains the number N (from 1 to 100).

Each of the following N lines is written first with some integer (between 0 and 10000), then a space, and then some text (max 20 characters).

It is required to display information in the same format, increasing the number in each line (except the first, where the number N is written) by 1.

Examples

ID 24659. AND ABOUT. Surname

Enter your first name, middle name and last name. Convert them to "initials-surname" format.

Input: The first line is a sentence. Words are separated by one space, there are no extra spaces at the beginning and end of the text.

Output: You need to output the modified string.
 

Examples

ID 30704. Замена подстроки

Найти в строке указанную подстроку и заменить ее на новую. Строка s, ее подстрока s1 для замены и новая подстрока  s2 вводятся.

P.S. Искомые подстроки в исходной строке не пересекаются.
P.P.S. В строках не содержатся пробелы.
P.P.P.S. Искомая подстрока может встречаться неоднократно.
P.P.P.P.S. Все буквы строчные.
P.P.P.P.P.S. Нет символов помимо строчных латинских букв.

На вход подаются 3 строки: s, s1, s2. Длина всех строк не превосходит 100.

ID 30705. Редактор скобочной последовательности

ID 34888. Cipher Julia

Julius Caesar used his own method of encrypting text. Each letter was replaced by the next alphabetically through K positions around the circle. It is necessary to determine the source text by the given encryption.

Input data:  the first line contains an encryption consisting of capital Latin letters. The second line contains the number K (\(1 <= K <= 10\)).

Output: You want to output the decryption result.
 

Examples

ID 23402. Arithmetic expression

In the first line of the input data the arithmetic expression is written in the form:

<number> <operation> <number> =

<Number> is a natural number not greater than 10000.

<Operation> - one of the characters +, -, *.

At the beginning of the line, at the end of the line, and between numbers and the operation sign, a number and the = symbol, there can be any number of spaces (or no spaces).

It is guaranteed that the length of the string does not exceed 200 characters.

 Display the result of evaluating the expression.

Examples

ID 24675. Arithmetic expression-1

Write a program that evaluates an expression consisting of three numbers and two characters (only «+» or «–» characters are allowed). The input is a character string representing an arithmetic expression. All numbers are integers.
 

Examples

ID 24676. Arithmetic Expression-3

Write a program that calculates an expression consisting of three numbers, three digits of arithmetic operations (signs «+», «–», « ;*» and «/») and  parentheses. The input is a character string representing an arithmetic expression. All numbers are integers. Operation «/» performed as integer division. 
 

Examples

ID 22025. Christmas tree decoration

Examples

ID 34959. Caesar's cipher

Gaius Julius Caesar (July 13, or from other sources, July 12, 100 or 102 BC — March 15, 44 BC e.) — ancient Roman statesman and politician, dictator, commander, writer. With his conquest of Gaul, Caesar expanded the Roman Empire. Caesar's activities radically changed the cultural and political face of Western Europe and left an indelible mark on the lives of the next generations of Europeans. Gaius Julius Caesar, having brilliant abilities as a military strategist and tactician, won the battles of the civil war and became sole ruler of Pax Romana.

Caesar often took paper and wrote letters during gladiator fights. He was asked, they say, how can you look at gladiators and write letters. To which Caesar replied: “Caesar can do three things at the same time: write, look, and listen.”

Julius Caesar used his own way of encrypting text to hide information from his enemies. Each letter was replaced by the next alphabetically through K positions around the circle.

Using modern computer technology, determine the source text from the given encryption.

Examples

ID 34963. The writings of Gaius Julius Caesar

Choosing the path of a politician and commander, Caesar had little time for creative work, but wrote compositions of various genres: the epic poem "Hercules", the tragedy "Oedipus Rex", the poem "Journey", " Notes on the Gallic War" and "Notes on the Civil War". Collections of his maxims, speeches, and letters were published. In addition, the great commander was interested in philology.

Taking a break from writing the poem, Caesar wrote down two lines one under the other and thought. Then he looked at the written lines and realized that the first line (S) could contain several times the second line (T). Gaius Julius Caesar decided to count all occurrences of the string T into the string S. Help him, write the appropriate program.

Examples

ID 34964. Task

Students who attended schools in ancient Rome solved various problems in the classroom. Here is one of the tasks:

101=1

8181515=4

1111112=0

8888888=14

1010101=3

7000007=?

Let the first number be x and the corresponding n.
Write a program that, given the number x, determines n.

Input 
The only non-negative x number not greater than 10¹⁰⁰¹.

Imprint
Output n.

Examples

ID 34965. Unpacking a line

Everyone knows that Caesar sometimes used cryptography, that is, a kind of cipher invented by himself.
Sometimes, to reduce writing time, Caesar used packing, the principle of which is to remove repeated letters and replace them with numbers that determine the number of repetitions.
We will consider only lines consisting of capital Latin letters. For example, consider the string AAAABCCCCCDDDD. This string can be represented as 4AB5C4D.
Write a program that takes a packed string and reconstructs the original string from it.
 

Examples

ID 38155. Final cost - 1

Imagine that you have been hired in the IT department of a chain grocery store. Starting next month, it is planned to introduce a 20% discount on some products. You are required to write a program for calculating the final cost of the purchase, taking into account all discounts.

A purchase is specified as a list of products, where each product is described in the format <ItemName> <price> x<quantity>. If the name of the product ends with the substring «sale», then the price of the product at the final calculation of the purchase is reduced by 20%, rounded down to the nearest whole number. So, for example, if the price of the goods was 12 rubles, taking into account the discount, it will be 9 rubles. The discount does not apply to other products.

The total cost of each product is calculated using the formula finalPrice⋅x, where finalPrice is the final price, possibly including discounts and rounding, and x is the quantity of the product in the shopping list. 
Your task is to calculate the total cost of the purchase.

Input
The first line contains the number n - the number of items in the purchase (1≤n≤1000).
The next n lines contain descriptions of the items in the purchase in the format: <ItemName> <price> x<number>.
The product name consists of no more than 20 lowercase Latin letters. Price - a natural number that is strictly greater than 1, but not more than 1000. Quantity - a natural number not greater than 100.

Imprint
Print one number - the total cost of the purchase.
 

Examples

ID 38156. Final cost - 2

Imagine that you have been hired in the IT department of a chain grocery store. Starting next month, it is planned to introduce a 20% discount on some products. You are required to write a program for calculating the final cost of the purchase, taking into account all discounts.

A purchase is specified as a list of products, where each product is described in the format <ItemName> <price> x<quantity>. If the name of the product not ends with the substring "fixed", then the price of the product at the final calculation of the purchase is reduced by 20%, rounded down to the nearest whole number. So, for example, if the price of the goods was 12 rubles, taking into account the discount, it will be 9 rubles. Products whose name ends with the  "fixed" substring are not eligible for the discount. 

The total cost of each product is calculated using the formula finalPrice⋅x, where finalPrice is the final price, possibly including discounts and rounding, and x is the quantity of the product in the shopping list. 
Your task is to calculate the total cost of the purchase.

Input
The first line contains the number n - the number of items in the purchase (1≤n≤1000).
The next n lines contain descriptions of the items in the purchase in the format: <ItemName> <price> x<number>.
The product name consists of no more than 20 lowercase Latin letters. Price - a natural number that is strictly greater than 1, but not more than 1000. Quantity - a natural number not greater than 100.

Imprint
Print one number - the total cost of the purchase.
 

Examples

ID 38190. Number of words

The input of the program receives a line of text, which may contain:
— uppercase and lowercase (i.e. large and small) Latin letters;
— spaces;
— punctuation marks: dot, comma, exclamation point and question mark;
— the character –, which in some cases stands for a dash, and in some cases — hyphen.
The word — is a sequence of consecutive Latin letters and hyphens, bounded at both ends. The beginning of a line, the end of a line, a space, a punctuation mark, a dash can act as delimiters. A dash differs from a hyphen in that letters are written to the left and to the right of the hyphen, and at least one side of the dash is either the beginning of a line, or the end of a line, or a space, or some kind of punctuation mark, or another dash.
Write a program that determines how many words are in a given line of text.

Input
A string of no more than 200 characters is entered.

Imprint
Print one number — the number of words that are contained in the source string.
 
Examples

ID 38203. Unspoken palindrome

Let's take an arbitrary word and perform the following operation with it: swap its first consonant with the last consonant, the second consonant with the penultimate consonant, and so on. If after this operation we again get the original word, then we will call such a word a silent palindrome. For example, the words sos, rare, rotor, gong, karaoke are implicit palindromes.

You need to write a program that determines if a given word is a silent palindrome.

Input
One word is entered.

Imprint
The program should output YES if the word entered is a non-vowel palindrome, and NO otherwise.

Examples

ID 38207. Number

Enter a natural number. It is required to separate the triples of its digits with commas (counting from the right).

Input
One natural number is entered, not exceeding 10¹⁰⁰.

Imprint
Output the same number, separating triples of digits with commas.

Examples

ID 38216. "My dad has more money"

Two people are playing this game. The first one says a number, then the second one says a number. If the number of the second is greater, then he won, otherwise (even if the numbers are equal), the first won. Help the second player – write a program that will successfully play this game for him.

Input
A natural number A is entered, which was named by the first player (in the number A  no more than 100 digits).

Imprint
Print one natural number – some (any!) winning move of the second player.

Examples

ID 38218. counting

The children decided to play catch-up, and in order to choose the driver, they stood in a circle and began to count. To do this, they used a counter. Pointing a finger in turn at each person standing in a circle, the counting utters one word, and the one who has the last word will lead. It is required to determine from this rhyme who will drive.

Input
The first line contains a counter. It consists of words written in Latin letters. The words are separated by one space. There are no punctuation marks, the line starts and ends with a letter. There are at least two words in the counter, and the length of the line does not exceed 100.

In the second line, in the same format, a list of schoolchildren's names is entered in the order in which they stand in a circle. Counting begins with the first student. There are at least two children, and the length of the string does not exceed 100.

Imprint
Print the name of the student who will drive.
 

ID 38220. good verses

Have you ever thought about how to distinguish good poetry from mediocre?

No? But the editor of a literary magazine does this every day, receiving tons of correspondence from young authors who want to become famous poets. Fortunately, recently most of the poems are sent by e-mail, so the editor had the idea to automate the process. He is firmly convinced that poetry is the better, the more accurate the rhyme in them. He considers two lines to be rhymed if they have the same last few letters. And the more letters match, the better the lines are rhymed. For example, the strings “stick” and “rope” only pairs of the last letters “ka” match, and the lines “olympiad” and “heaven and hell” four letters match (we skip spaces). Therefore, the second rhyme is better. The editor believes that in a quatrain (four lines) the first line should rhyme with the third, and the second – from the fourth. For each of these two pairs of strings, it counts the number of matching last characters and chooses the largest of these two numbers. He calls the resulting number the quality coefficient of the poem – the higher it is, the more likely the poem is to be published. Help the editor – write a program that determines the quality of a poem. And who knows, maybe thanks to your efforts, the world will get acquainted with brilliant poems (see the first example).

Input
The input is 4 non-empty lines, each of which consists of no more than 100 lowercase Latin letters (the poem has already been pre-processed: all spaces and punctuation marks have been removed from it, and capital letters have been made lowercase).

Imprint
Print one number – poem quality index.
 

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 38240. Multiplications

An algebraic expression is given, consisting of natural numbers, variables (a, b, c, ..., z) written in lowercase Latin letters, signs of arithmetic operations  + ,  - ,  *   (multiplication) and  *  *  (exponentiation). Moreover, if after the number there is a variable, then the multiplication sign can be skipped.

It is required to calculate how many multiplications and how many exponentiations are in this expression.

Input
A string of up to 200 characters and at least one character is entered. It is a valid algebraic expression.

Imprint
Print two space-separated numbers: the number of multiplications and the number of exponentiations.

Examples

ID 38246. Spy things

Alice and Bob — very experienced spies. Best of all, they manage to find passwords to access various secret data. This time, too, Alice received a message from Bob saying that the key was a number, followed by the number itself. Bob also wrote that the key number should be divisible by 9. When Alice tried to enter the received password, it turned out that it did not fit. Alice trusts Bob very much, and therefore she decided that Bob could only make a mistake in one digit of the password. Since Alice does not have much time, she decided not to ask Bob for the correct answer, but to try all the numbers that could be a password, i.e. all such numbers that can be obtained from the number that Bob sent by replacing exactly one of its digits and divisible by 9. Alice turned to you for help. Write a program that will offer Alice all possible passwords.

Input
The input contains a single number P (1 ≤ P ≤ 10⁹) — the number that Alice received in the message from Bob. It is guaranteed not to start from zero.

Imprint
Print in a column all the possible passwords that Alice needs to try out, in random order. None of the numbers you receive should start from zero. All possible passwords must contain the same number of digits as the original number received by Alice.

Examples

ID 38257. Too much caffeine

Arthur was always very afraid to meet girls. It's not even about Arthur's natural shyness, and not even so much about the fact that Arthur doesn't know what to talk about with girls. It’s just that Arthur hasn’t pronounced the letter “p” since childhood; and is very shy about it. Therefore, Arthur tries not to utter words once again that contain this hated letter.

One day, friends introduced Arthur to a girl named Nina (oh, what a beautiful name!). She was charming and very talkative, so Arthur hardly needed to find the words — she filled the awkward silence for him. Of course, he invited her to a cafe for a cup of coffee. Arthur even thought through all his lines in advance: "Happy to see you," "You're amazing today," "Yes, of course, I'm listening to you carefully," "What's next?", "The bill, please." and, of course, "I'll call you one of these days, don't be bored."

But, as you know, there are no ideal plans. Everything went like clockwork, but suddenly, sitting at a table in a cafe, Nina said that she had not slept terribly and would not refuse N cups of coffee. And then Arthur realized that he had not thought in advance how he would order. It's understandable to say something like, "How many cups of coffee, please?" Obviously you need to order at least N + 1 cup — so that Nina gets N cups, and drink it herself, but here's exactly how much — Arthur doesn't know. He doesn't have much money, so he doesn't want to order more than what is vital to avoid exposure.

Help Arthur — count how many cups of coffee he should order.

Input
One integer N is entered (1 ≤ N ≤ 2999).

Imprint
Print one number — the number of cups of coffee that Arthur should order.

Examples

ID 38264. Telegrams Matroskin

When Uncle Fyodor went home to the city, Matroskin and Sharik remained in charge of the household. But since Uncle Fyodor was very worried about the affairs in Prostokvashino, they agreed that every week Matroskin would write a letter with a report on the affairs. Pretty soon Matroskin realized that the letters were taking too long, so he decided to send telegrams. Usually the reports are very long, so Matroskin had to send several telegrams. To make it easier for Uncle Fyodor to understand the incoming telegrams, Matroskin follows the following rules:

Each telegram should contain no more than 140 characters, including spaces and punctuation.
The source text must be split into telegrams by spaces, while the space at which the telegram is split is destroyed.
If the telegram is not the last one, add three dots to the end of it.
If the telegram is not the first, add three dots to its beginning.
To save money on sending telegrams, Matroskin wants to split the text into as few as possible.

Help Matroskin split the source text into as few telegrams as possible according to the above rules.

Input
The input is a string of small Latin letters and spaces. It does not start or end with spaces, and no two spaces can be consecutive. The length of the string does not exceed 10000.

Imprint
In the first line print the number N – the number of telegrams into which the original string should be split. In the next N lines print the telegrams themselves. If it is impossible to pass the text in the given way, print −1.

 

Examples

ID 38271. Words won't get through

Children, as you know, are starting to use the Internet earlier and earlier. Now, when they have questions, they do not run to their parents, but go to their favorite search engine and find out the answer on the Internet. But what if they accidentally find something that is too early for them to know? Or maybe it's better not to know at all?

In one country, this problem was solved very simply: a list of words prohibited for use on the Internet was created. After all, it is obvious that an article that mentions some bad word cannot teach a child anything good. Any site containing at least one word from this list is now subject to instant blocking. An innocent child will never stumble upon something that is too early for him to know — There is simply no such article on the Internet. But the evil site owners came up with a way to get around this ban: if instead of some letters you write numbers that look like them, you can still read this text, and the robot that checks sites for suitability does not recognize the forbidden — because formally it is not on the site.

Your task — help the government of this country protect children from harmful information. Write a program that will check if a given string contains a forbidden word, taking into account the possible cunning of site owners. Site owners have been known to sometimes make the following substitutions: e  3, o  0, i  1, t  7, a  4, s  5.

Input
The first line of the input contains the string — text from the site. The second line of the input contains another string — forbidden word. The first line consists of small Latin letters and numbers, the second line consists only of small Latin letters. The length of each line does not exceed 100.

Imprint
Print "YES" if the forbidden word occurs as a substring in the string from the site, and "NO" otherwise. It is possible that in the line from the site, some letters were initially replaced with numbers in accordance with the above rules.
 

Examples

ID 38293. substring palindrome

Marina loves palindromes very much. Palindrome — is a string that reads the same from left to right and from right to left, such as « noon "," rotator » or " radar».

Marina wrote a string s on the board, consisting of n lowercase Latin letters s₁ s₂ ... s_n . A substring of the string s is the string s _{ls l + 1} ... s_r for some 1 ≤ l≤ r ≤ n. Marina searches the string s for the longest possible substring that is a palindrome. For example, in the line " rotateradar » such a substring would be « radar».

Vova wants to change the line written by Marina so that the palindrome substring is as long as possible. He can either leave the string intact, or change exactly one letter in it to another. For example, if the line " rotateradar » change the sixth letter to " o », you get the string « rotatoradars », in which the maximum palindrome substring « rotator » has length 7 . A palindrome substring of greater length cannot be obtained.

Help Vova determine the maximum length of a palindrome substring he can get.

Input
The first line of the input contains a natural number n — the length of the string Marina wrote ( 1 ≤ n ≤ 100 ).

The second line of the input contains the string itself, consisting of n lowercase Latin letters.

Imprint
In the output file print a single number — the maximum length of a palindrome substring that Vova can get.

Examples

ID 38311. sandwich method

Secret agency "Super-Secret-no" decided to use the "sandwich method" to encrypt the correspondence of its employees. First, the letters of the word are numbered in this order: the first letter is number 1, the last letter is number 2, the second – number 3, penultimate – number 4, then the third … and so on for all letters (see figure). Then all the letters are written in the cipher in the order of their numbers. A "sharp" sign is added to the end of the ciphered word. (#) which   cannot be used in messages.

For example, the word "sandwich" will be encrypted in «shacnidw#».



Unfortunately, the "Super-Secret-no" programmer only wrote the encryption program and quit. And now the agents cannot understand what they wrote to each other. Help them.

Input
A word encrypted using the sandwich method is entered. The length of the word does not exceed 20 letters.

Imprint
Output the deciphered word.

Examples

ID 38317. euphonious word

All letters of the Latin alphabet are divided into vowels and consonants. The vowels are: a, e, i, o, u, y. The remaining letters are consonants.

A word is called euphonious if this word does not contain more than two consonants in a row and no more than two vowels in a row. For example, the words abba, mama, program — harmonious, and the words aaa, school, search — dissonant.

The word is entered. If this word is dissonant, then it is allowed to add any letters to any place in this word. Determine the minimum number of letters that can be added to this word to make it euphonious.

Input
A word is entered, consisting only of small Latin letters. The word length does not exceed 30 characters.

Imprint
Print the minimum number of letters that need to be added to this word to make it euphonious.
 

Examples

ID 38333. Phone numbers

Phone numbers in the mobile phone's address book have one of the following formats:

+7<code><number>

8<code><number>

<number>

where <number> — is seven digits, and <code> — it's three digits or three digits in parentheses. If the code is not specified, then it is considered to be 495. In addition, the telephone number entry may contain the “-” between any two digits (see example).

At the moment, Vasya has only three phone numbers in his address book, and he wants to add another one there. But he cannot understand if such a number is already recorded in the phone book. Help him!

Two phone numbers match if they have the same codes and the same numbers. For example, +7(916)0123456 and 89160123456 — it's the same number.

Input
The first line of the input contains the phone number that Vasya wants to add to his phone's address book. The next three lines contain three phone numbers that are already in the address book of Vasya's phone.

It is guaranteed that each of the entries corresponds to one of the three formats given in the condition.

Imprint
For each phone number in the address book print YES (in capital letters) if it matches the phone number Vasya wants to add to the address book or NO (in capital letters) otherwise.
 

Examples

ID 38338. Strings

Given three strings consisting of lowercase Latin letters. With these strings, you can perform the following operations: either replace one character of the string with two of the same characters (for example, replace the character "a" with "aa"), or, conversely, replace two consecutive identical characters with one of the same character.

It is necessary to use these operations to make all three strings equal to some other common string S, or to determine that it is impossible to do so. At the same time, it is necessary to minimize the total number of operations.

Input
The program receives as input three strings consisting of lowercase Latin letters. The length of each line does not exceed 100 characters.

Imprint
If it is possible to make all three strings equal using the indicated operations, print a string S such that the total number of operations required to convert all three given strings to the string S will be minimal. If this cannot be done, the program should print a single word IMPOSSIBLE (in capital letters).

Examples

ID 38446. howl

The leaders of the famous Mumba Yumba tribe decided to come up with a new battle cry for their warriors. At the same time, they decided that the cry should consist of exactly N letters (there are M letters in the alphabet of the tribe). Also, after much research, it was found out that if the word s_i   (the word – is a sequence of letters of the alphabet, no longer than three characters) is found in the scream, then this scream instills f _{in the enemy i} units of fear. If a cry includes several words, then their “terrible” summed up. For example, if a yell contains the words s_i and s_j, then the yell instills f_i+f_j units of fear . 
Given N, M, the alphabet and the list of words s_i, it is required to compose the most terrible scream. 

Input:
The first line contains three numbers – N, M and K (0<N≤100, 0<M<25, 0<K≤100), where K– number of scary words. The next line contains the alphabet – a string of M lowercase Latin letters. Next, K lines contain information about the words – the word itself and, separated by a space, one number denoting the scariness of this word (0 < f_i ≤ 10000).

Output:
In the output file, you need to output the scariness of the received scream and on the next line – the scream itself.

Examples

ID 33648. Wrong palindrome

A palindrome is a word that reads the same way both from left to right and from right to left, for example, in English such words are “radar”; and «racecar».
Sveta is studying English and decided to take part in a distance competition for English speakers. But, when she wrote the answer to the task “find the longest word that is a palindrome”, she made a mistake and pressed one extra key on the keyboard.
Determine which letter needs to be removed in the word Sveta has typed so that this word becomes a palindrome.

Input
The program receives as input a string of lowercase English letters containing at least 2  and no more than 100,000 characters.

Imprint
The program should output a single number – the number of the letter in the string that when removed becomes a palindrome. If removing any letter does not make the word a palindrome, the program should print the number 0.

Examples

ID 38481. Iroha loves strings

Iroha has a sequence of N strings s1, s2, .. , sN. Each line is L long. Iroha wants to concatenate all strings to get a very long string. Among all the strings it can get in this way, find the lexicographically smallest one. 

We will assume that the string s = s1s2...sn is lexicographically less than the string < code>t = t₁t₂...t_m if one of the following conditions is true:
- there is an index i (\(1<=i<=min(n,m)\)) such that \(s_j =t_j \), for all indices j (\(1<=j<= i\)), and \(s_i <t_i \);
-  \(s_i=t_j\) for all i (\(1<=i<=min( n,m)\)), and \(n<m\).


Input
The first line contains numbers N and L. Next are the lines s1, s2, .., sN< /sub>, each on a separate line.

Imprint
Print the lexicographically smallest string that Iroha can create.
 

Examples

ID 38484. Keyboard Gromozeka

Gromozeka built his own keyboard. Designed for simplicity, this keyboard has only 3 keys: 0 key, 1 key and backspace key.

Gromozek decided to test his own keyboard in a text editor. This editor always displays one line (possibly empty). When the editor starts, this line is empty. When you press each key on the keyboard, the following changes occur in the line:
- 0 key: 0 character will be inserted to the right of the string;
- 1 key: 1 character will be inserted to the right of the string;
- backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is removed.

Gromozeka launched the editor and pressed these keys several times. You are given a string s which is a record of keystrokes in order. In this string, the character 0 represents the key 0, the character 1 represents the key 1, and the character  B stands for the backspace key. Determine which line is now displayed in the editor?

Input
The input is the string s (\(1 <= len(s) <=10\)). The string consists of the characters 0, 1 or B.

Imprint
Display the answer to the problem.
 

Examples

01B0

00

0BB1

1

ID 38488. beautiful string

Let s be a string consisting of lowercase letters. We will call a string s beautiful if each lowercase letter of the English alphabet occurs in it an even number of times. Given the string s, determine if it is beautiful.

Input
The input is a string. The length of the string is not zero and not more than 100 characters. The string consists only of lowercase English letters (a-z).

Imprint
Print Yes if s is pretty, otherwise print No.
 

Examples

ID 38510. Dream

Given a string S consisting of lowercase English letters and an empty string T. You can add one of the following words to the end of the T line: dream, dreamer, erase and eraser. Determine if it is possible to get S = T.

Input
The input is the string S (\(1<=S<=10^5\)), consisting of lowercase English letters (a-z).

Imprint
If it is possible to get S = T, print YES. Otherwise, print NO.
 

erasedream

YES

dreameraser

YES

dreamer

NO

ID 38519. Haiku

As a New Year's gift, Gromozeka received a string s of length 19 of the following format:
[five lowercase English letters], [seven lowercase English letters], [five lowercase English letters ].
Gromozeka wants to convert the comma-separated string s to a space-separated string. Write a program to do the conversion for him.

Input
The input is one string s, the length of the string is exactly 19 characters. The sixth and fourteenth characters in s are ,. The remaining characters are lowercase letters of the English alphabet (a-z).

Imprint
Output string after conversion
 

Examples

happy,newyear,enjoy

happy new year enjoy

ID 38522. Decrease-enlarge

You have an integer variable x. Initially \(x = 0\). Someone gave you a string S of length N, and using that string you performed the following operation N times. In the ith operation, you incremented x by 1 if Si = I, and decrement x by 1 if Si = D. Find the maximum value x takes during operations (including before the first operation and after the last operation).

Input
The first line contains the number N (\(1<=N<=100\)), the second line contains the string S . The length of the N string. The string contains only the characters I and D.

Imprint
Print the maximum x value obtained during the operations.
 

Examples

5
IDID

2

7
DDIDDII

0

ID 38526. A-Z line

Gromozeka decided to build a string that starts with A and ends with Z by extracting a substring of the string s (that is, the consecutive part of s >). Find the longest string that Gromozeka can construct. It is guaranteed that there is always a substring s that starts with A and ends with Z.

Input
The input is the string s (\(1<=len(s)<=200000\)), consisting of uppercase English letters ( A-Z).

Imprint
Display the answer to the problem.
 

Examples

ID 38616. two identical letters

Given a line. It is known that it contains exactly two identical letters. Find these letters. It is guaranteed that only one type of letter is repeated.

Input
The input is 1 line.

Imprint
You need to print  a letter that occurs twice in a string.
 

Examples

ID 38626. Arithmetic cookies. Very easy task

There is always an integer in Gromozeka's mind. Initially, in Gromozeka's mind, the integer is 0. Now Gromozeka is going to eat four cookies, each of which has either + or - written on it. When he eats a cookie with the symbol +, the integer in his mind increases by 1; when he eats a cookie with a - character, the integer in his mind decreases by 1. The cookies that Gromozeka is about to eat are given to you as a string S, i th character in S is i is the cookie he eats. Find the integer in Gromozeka's mind after he has eaten all the cookies.

Input
The input is a string of 4 characters, each of which is equal to + or -.

Imprint
Print an integer in Gromozeka's mind after he has eaten all the cookies.
 

Examples

+-++

-+--

----

ID 38653. Lots of formulas

You are given a string S consisting of numbers from 1 to 9 inclusive. You can insert the character + at some positions (perhaps none) between two digits in this string. Here, the + character must not appear consecutively after insertion (i.e., there must not be two or more +  characters in a row). All rows that can be obtained in this way can be evaluated as formulas. Evaluate all possible formulas and print the sum of the results from all possible formulas.

Input
The input is a non-empty string S, consisting of numbers from 1 to 9 inclusive. The string is limited to 10 characters.

Imprint
Print the sum of the results obtained by evaluating all possible formulas.
 

Examples

ID 23404. Статистика

ID 33237. Average score in subjects - 2

ID 38717. Students without triplets

Print the last names and first names of students who do not have triples (as well as twos and stakes).

Input
First, the number of students n is given, then n lines, each of which contains the last name, first name and three numbers (grades in three subjects: mathematics, physics, computer science). The data in a line is separated by a single space. Ratings take a value from 1 to 5.

Imprint
It is necessary to output pairs of surname-first name, one per line, separating the surname and first name with one space. No ratings required. The output order must be the same as in the original data.
 

Examples

ID 38718. Three best

Identify the three students with the best GPA in three subjects. Print the first and last names of these students. If at the same time, several students have the same average score as the average score of the student who "took 3rd place", then you need to print them all.

Input
First, the number of students n is given, then n lines, each of which contains the last name, first name and three numbers (grades in three subjects: mathematics, physics, computer science). The data in a line is separated by a single space. Ratings take a value from 1 to 5.

Imprint
It is necessary to output pairs of surname-first name, one per line, separating the surname and first name with one space. No ratings required. The output order must be the same as in the original data.
 
 

Examples

ID 38720. Sort by GPA

Print the last and first names of students in descending order of their GPA.

Input
First, the number of students n is given, then n lines, each of which contains the last name, first name and three numbers (grades in three subjects: mathematics, physics, computer science). The data in a line is separated by a single space. Ratings take a value from 1 to 5.

The total number of students does not exceed 100001.
Imprint
It is necessary to output pairs of surname-first name, one per line, separating the surname and first name with one space. No ratings required. If several students have the same average scores, then they should be output in the order specified in the input data.
 

Examples

ID 38944.

ID 38954. Boring lecture

Lyosha was sitting at the lecture. He was incredibly bored. The lecturer's voice seemed so distant and inconspicuous...

In order not to fall asleep completely, he took a piece of paper and wrote his favorite word on it. A little lower, he repeated his favorite word, without the first letter. Even lower, he again wrote his favorite word, but this time without the first and last letters.

Then the thought came to him — there is still a lot of time until the end of the lecture, why not continue writing this word in every possible way without some part from the beginning and some part from the end?

After the lecture, Lyosha told Max how wonderfully he had passed the time. Max became interested in counting how many letters of each type are found in Lyosha's leaflet. But unfortunately, the leaflet itself disappeared somewhere.

Max knows Lyosha's favorite word well, and he doesn't have as much free time as his friend, so help him quickly recover how many times Lyosha had to write down each letter.

Input
The input is a string consisting of lowercase Latin letters — Lyosha's favorite word.

The string length is between 5 and 100 000 characters.

Imprint
For each letter on Lyosha's piece of paper, print it, and then, separated by a colon and a space, how many times it occurs in the words Lesha wrote out (see the output format in the examples). The letters must be in alphabetical order. Letters that do not appear on the sheet do not need to be displayed.

Examples

ID 39356. Get OK

Given a string S of length N, consisting of the characters S, T, O and K. Answer Q requests like the following.
Query i(1 <= i <= Q): for given integers li and r i (1 <= l_i< r_i <= N),  the substring S is considered, starting at index li and ending at index ri < /sub> (both inclusive). You need to determine how many times OK  occurs as a substring in this string?
 

Explanation

ID 39535. hungry pawn

Gromozeka respects chessboard games. Gromozeka has a hungry pawn on a regular 8x8 board. A hungry pawn eats some opponent’s piece every move (i.e. it can move diagonally forward 1 square to the right or left, it cannot move back). Gromozeka, without looking at the board, learned to determine whether a hungry pawn can move from one square of the board to another. It is impossible to turn into a queen to a hungry pawn.
Write a program with which you could also easily check Gromozeka.

Input
The program receives as input two cells of the chessboard in chess notation. First, the cell where the hungry pawn stands, and then, after a gap, the cell where the hungry pawn must go.

Imprint
Print the word YES (in capital letters) if a hungry pawn can move from the first cell to the second, and NO otherwise.
The board has a size of 8x8, the verticals are numbered in small Latin letters from a to h, the horizontals are numbered from 1 to 8. The starting and ending cells do not match.
 

Examples

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 39618. File analysis

The text file consists of no more than 10⁶ characters and contains only uppercase Latin letters (ABC…Z). The text is divided into lines of various lengths. We call a subsequence original if it is bounded on the left by the substring  AB, and on the right by the substring BA  (these substrings are also included in the subsequence) and there are no other letters in this subsequence A and B. The original subsequence cannot start on one line and end on another.
Determine how much  total  original subsequences in the entire file, as well as the length of the maximum of them.

In your answer, write together two integers, first the number of original subsequences, then the length of the maximum of them.

Example
Source file:
AAABCAABCBAA
ZZABZZZBABCBA
QRABUTUUBA
There are 4 original subsequences in this example (ABUTUTBA, ABZZZBA, ABCBA, ABUTUTBA)
The longest subsequence (ABUTUTBA) has a length of 8.
Answer: 48


Assignment file

ID 39830. Indexes and slices

The input of the program is the string s.  Using character references by index and string slices, print the following substrings:

1. all characters from index 3 to the middle of the string inclusive (if the length of the string is odd, do not take the middle character);
2. last character;
3. all characters with even indexes (0, 2, ...);
4. all characters with odd indices (1, 3, ...);
5. all characters except the last one;
6. all characters except the first one;
7. all characters in reverse order;
8. all characters in reverse order, starting with 3 from the end, and except for the first two;
9. all characters of the first half in reverse order, except for the first (if the length of the line is odd, do not take the middle character);
10. slicing copy the entire string s to the string s2.

Examples

ID 39832. Lines with vowels and consonants

Write a vowels_count function that takes a string and counts the number of English vowels in it.
English vowels: a, e, i, o, u, y.

Using this function, define two lines:
s1 - the string with the largest number of vowels (if there are several such strings, take the one that occurs first).
s2 - the string with the smallest number of consonants (if there are several such strings, take the one that occurs first).


Input
The first line contains a natural number n (1 < n <= 10) - the number of lines. Next come n lines. Each line consists of small English letters and spaces.

Imprint
Print two lines on the screen: first, the line s1, then, on a new line, s2. Align the smallest of these strings with the largest one by adding the characters '*'.
 

Examples

ID 40062. What is missing?

You are given a string S exactly 9 characters long. Each character in the string is any of the digits from 0 to 9. All characters in the string are different. Print the missing digit in the string.

Input
The input is a string consisting of numbers. 

Imprint
Display the answer to the problem
 

Examples

023456789

1

459230781

6

ID 40082. Step right

There are 4 squares drawn horizontally in a row.

You are given a string S of length 4, consisting of 0 and 1.
If the ith character of S is 1, there is a person in the ith square on the left;
if the ith character of S is 0, there is no person in the ith square on the left.

Now everyone takes a step to the right at the same time. That is, they move to the next cell on the right. With this move, the person who was originally in the far right square is eliminated. 
Determine if a person will remain on each cell after the move.

Output the result as a string in the same format as S. (See the input/output example for clarity.)

Input
The input is a string S of length 4, consisting of 0 and 1.

Imprint
Output a string of length 4. The i-th character should be equal to 1 if there is a person in the i-th square on the left after the move, and 0 otherwise.
 

Examples

1011

0101

1111

0111

ID 42452. When is Saturday

One day, tired from going to school, Tommy wanted to know how many days were left until Saturday. We know that this day was a weekday, and the name of the day of the week was S (in English). How many days remained until the first Saturday after this day (counting the Saturday itself, but not counting the day S)?

Input
The input is the string S (S can be  Monday, Tuesday, Wednesday, Thursday or Friday).

Imprint
Display the answer to the problem

Use nested conditions (elif for Python and else if for other languages).
 

Examples

Wednesday

3

ID 23086. Characters before comma

An offer has been given. Print all its characters preceding the first comma. If there are no commas in the sentence, then output the entire sentence. 

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is the original sentence.

Output: you need to print all the characters of the sentence that precede the first comma, if there are no commas, print the entire sentence

Input and output example

ID 23087. First "e"

Given a sentence that contains several letters 'e' (English). Find the serial number of the first one.

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is the original sentence.

Output: you need to output the number of the first letter "e" (eng) in a sentence

Input and output example

ID 23088. Find "a"

ID 23089. Changeling

The word is given. Check if it is a "changeling", (that is, it is read the same way both from the beginning and from the end).

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is a word.

Output: need to output the word "YES" if the word is a shifter, and the word "NO" - otherwise

Sample input and output

ID 23090. How many "i"

Given a string divided into sentences. All sentences end with a dot. Determine the number of letters 'i' in the first sentence. 

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The program receives a string as input.

Output: need to print the number of letters 'i' in the first sentence.

Sample input and output

ID 23093. How many "o"

A sentence is given that does not contain the "-" symbol. Determine the number of letters "o" (English) in the first word. There may be spaces at the beginning of a sentence.

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: a single line specifies the original sentence.

Output: need to print the number of letters "o" (English) in the first word.

Sample input and output

ID 23092. Prefix

Two words are given. Determine how many initial letters of the first word match the initial letters of the second word

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: the first line contains two words separated by a space
Output: need to print the number of letters matching from the beginning

Sample input and output

ID 23094. How many "n" before the decimal point

An offer has been given. Count the number of "n" letters preceding the first comma of the sentence. 

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is the original sentence.

Output:

Sample input and output

ID 23095. First identical

An offer has been given. Determine the serial numbers of the first pair of identical neighboring characters. If there are no such characters, then display the word NO.

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is a  sentence.

Output: you need to output serial numbers of the first pair of identical adjacent characters separated by a space, or the word "NO" - if there is no such pair of adjacent characters

Sample input and output

ID 23091. same at the beginning

Given a sequence of characters, at the beginning of which there is a certain number of identical characters. Determine this quantity.

Solve the problem without using the built-in string functions, except for a function that returns the length of a string.

Input: The first line is a sequence of characters.

Output: should print the number of identical characters at the beginning of the string.

Sample input and output

ID 4999. How many words in a sentence

The line is written as a sentence. Write a program that will determine the number of words in it. There is only one space between words in the sentence, there are no spaces at the end and at the beginning.

Sample input and output

ID 38612. Change case

Change the case of the character. If it was a lowercase English letter, make it a capital letter; if it was a capital English letter  - lowercase.


Input
Single character c.

Imprint
You need to output  the resulting character.
 

Examples

ID 4995. Replace symbols

One line contains a character and some text. Write a program that replaces all even-numbered characters in text with a given character. Character numbering starts from 1.

Sample input and output

ID 4994. Replacing one with another

One line contains two characters and some text separated by a space. Write a program to replace all letters in the text that match the first character with the second.

Sample input and output

ID 4998. Symbols in the right places

A number and some text are written in one line separated by a space. Write a program that outputs from the text those characters whose numbers are multiples of a given number (numbering starts from 1).

Sample input and output

ID 5000. We count the numbers

Given a line. Write a program that determines if a given string contains digits.

Sample input and output

ID 5002. Word with the desired letter at the end

A character and a sentence are written in one line separated by a space. Write a program that counts how many words in a sentence that end in a given character. There is only one space between words in the sentence, there are no spaces at the end and at the beginning.

Sample input and output

ID 39378. String shift

In a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string. For example, a left shift on the string abcde results in bcdea, and two shifts to the right by abcde results in deabc.

Given a non-empty string S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts, find the lexicographically smallest string and the lexicographically largest string.

Input
The input is a single string S. S consists of lowercase English letters. 1 <= |S| <= 1000, where |S| is the length of the string S.

Imprint
Print the lexicographically smallest string in the first line, and the lexicographically largest string in the second line.
 

Examples

ID 42693. Big numbers

Let S(n) be the sum of the decimal digits of the integer n. For example, S(123)=1+2+3=6.

Given two three-digit integers A and B, find the greater of S(A) and S (B).

Input
The input is a single string containing two integers A and B (100 <= A, B <= 999).

Imprint
Print the larger value of S(A) and S(B). If they are equal, print S(A).

Please note that division operations cannot be used when solving the problem.

Examples

ID 42698. Copy n-ok

Let  \(N(n,k) = n+\overline{nn}+\overline{nnn} + ... +\underbrace{\overline{n..n }}_{k}\). Given the value n and k, calculate the value N(n, k).

Input
The program receives two lines as input. The first line contains a natural number n (1<=n<=9), the second line contains a natural number k (1 <= k <= 10).

Imprint
Display N(n, k) as an expression and an answer.
 

Examples

1
3

1+11+111=123

ID 43798. Substring

In this problem, you need to find the longest substring of the given string, such that each character occurs in it no more than k times.

Input
The first line contains two integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , where n – the number of characters in the string. The second line contains n characters – the given string, consisting only of lowercase Latin letters.

Imprint
In the output file print two numbers – the length of the searched substring and the number of its first character. If there are several solutions, print any one.

Examples

ID 44032. When is the New Year?

Tommy loves Christmas very much! December 31 this year falls on a Saturday. Tommy wanted to know how many days until December 31st. We know that today is a weekday S (in English) and December 31st is already this week on Saturday. Help Tommy determine how many days until December 31 after today (counting December 31, but not counting today S)?

Input
The input is the string S (S can be  Monday(Monday), Tuesday(Tuesday ), Wednesday(Wednesday), Thursday(Thursday) or Friday(Friday)).

Imprint
Display the answer to the problem

Use nested conditions (elif for Python and else if for other languages).
 

Examples

Wednesday

3