Dictionaries

Tweet

Share

Plus

Pin

Problem description Progress

ID 32981. Sale

Темы: "Two Pointers" Dictionaries

The store is having a New Year sale – prices of all goods are reduced by 25%. It turned out that initially all prices were divisible by 4, so after the price decrease, all prices are also expressed as an integer. In the evening before the sale, the merchandiser removed the price tags from all the goods and printed another price tag with a reduced price for each product. He left all the price tags on the table, hoping to hang them up in the morning. But when he came to the store in the morning, he found that the cleaning lady had mixed all the price tags together, and now he needs to separate the old price tags from the new ones.

Help him solve this problem.

Input
The first line of the input contains the total number of price tags N, 2 <= N <= 10⁵,

N – even number. The following N lines contain positive integers not exceeding 10⁹, in non-decreasing order, one per line – numbers written on all price tags (both old and new). It is guaranteed that the input data is correct, that is, the solution exists.





Imprint

The program should output N/2  integers in non-decreasing order – the cost of goods after price reduction.



 
Examples




#
Input
Output
Note




1

6

30

40

42

45

56

60


30

42

45


Before the sale, the prices of the goods were 40, 56, 60, after the price reduction

these products have become equal to 30, 42, 45.

ID 37788. Synonyms

Темы: Dictionaries

Synonym dictionary — describes synonymous series, that is, groups of words that have the same or fairly close meaning. The dictionary is often used synonymously by copywriters.
You have a dictionary consisting of pairs of synonymous words. All words in the dictionary are different. Output a synonym for the proposed word.

Input
The program receives as input the number of pairs of synonyms N. This is followed by N lines, each containing exactly two synonym words. The last N+1 line is followed by one word.

Imprint
Write a synonym for the given word.

Note
Use a dictionary in your program.

Examples

#	Input	Output
1	2 Dictionary Map List Array Array	List

ID 29635. Online store

Темы: Dictionaries

Given a database of sales of some online store. Each line of the input file is a record of the form:
Buyer item quantity,
where Buyer— buyer's name (string without spaces), product — product name (string without spaces), quantity — number of items purchased.

Create a list of all customers, and for each customer, count the number of units of each item they purchased.

Input
The first line of the input file contains the number N (\(1<=N<=100000\)) —number of records contained in this database data. Purchase details are entered in the specified format.

Imprint
Print a list of all customers in lexicographical order, after the name of each customer print a colon, then list the names of all goods purchased by this customer in lexicographic order, after the name of each item print the number of units of goods purchased by this customer. Information about each product is displayed in a separate line.

Example

#	Input	Output
1	6 Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5	Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5

ID 29634. File system

Темы: Dictionaries

The file system of one supercomputer was infiltrated by a virus that broke file access control. For each N_i file, it is known what actions can be accessed with it:

record W

read R

launching X

You need to regain control over file permissions (your program will need to return OK for each request if a valid operation is being performed on the file, or Access denied if the operation is invalid).

Input
The first line contains a number N (1 <= N <= 10000) - number of files contained in this file system.

The following N lines contain the names of files and the operations allowed with them, separated by spaces. The file name is limited to 15 characters.

The following is the number M (1 <= M <= 50000) - number of file requests.

The last M lines contain a query like Operation File. Any number of queries can be applied to the same file.

Output
For each of the M requests, print Access denied or OK.
on a separate line

Example

#	Input	Output
1	4 helloworld.exe R X pinglog W R nya R goodluck X W R 5 read nya write helloworld.exe execute nya read ping log write pinglog	OK Access denied Access denied OK OK

ID 37852. Sorting a dictionary

Темы: Dictionaries

An alphabetic-frequency dictionary is a frequency dictionary in which words with their frequency (occurrence) are arranged alphabetically.
Build a dictionary sorted by word frequency, in which words are arranged in descending order of their frequency of occurrence, to the right of each word should be indicated how many times it occurs in the text. If the number of words is the same, the sort is word by word in lexicographic order. The sign of the end of the text is "END!".

Input
Lines of text are given as input. The last line contains one single word "END!" and is a sign of the end of the text.

Imprint
Display all the words on the screen, indicating, separated by a space, how many times this word occurs in the text. Each word on a separate line.

Examples

#	Input	Output
1	one two three one two END!	two 2 one 2 three 1

ID 30658. The final

Темы: Dictionaries

Programming competitions are held annually in St. Petersburg, Barnaul and some cities of the near abroad. These competitions are held as part of the student world championship in programming, organized by one of the most respected associations ACM (Association for Computing Machinery). At these competitions, teams from the North-Eastern European Region NEERC (North-Eastern European Regional Contest) are selected. Every year, the organizers of the competition face the problem of determining the teams that will be invited to participate in the finals of the World Programming Championship. According to the new rules, no more than N teams representing NEERC go to the final. In addition, more than k teams cannot pass from one university. At the same time, from all such sets, the one in which the sum of places occupied by these teams in the semifinal competitions is the minimum possible is selected. Your task is to determine which teams will be invited to participate in the World Cup final based on the final protocol of the semi-final competitions and the numbers N and k.

Input

In the first line of the input file there are three natural numbers Р (1 ≤ P ≤ 100000) — the number of teams participating in the semi-final, N (1 ≤ N ≤ P ) and k (1 ≤ k ≤ P ) . The next P lines, one per line, list the names of the universities whose teams took the corresponding places. The name of the university contains lowercase and uppercase Latin letters and spaces. The length of the university name does not exceed 30 characters. The next line lists the team numbers of the respective universities. Thus, if the name of the university is written in the i -th line (2 ≤ i ≤ P + 1) , then this team took i - 1 place in the semi-finals and has a number written in i - 1 place in P + 2 line.

Output

In the output file print the names of the teams invited to participate in the finals of the World Programming Championship, sorted by the place occupied in the semi-finals. As the name of the team, print the name of the university followed by a space #the team number.

Example

#	Input	Output
1	9 5 2 Fantasy University Crazy University Fantasy University Fantasy University Very Good U Good U Very Good U Crazy University Good U 1 1 2 3 2 1 1 2 2	Fantasy University #1 Crazy University #1 Fantasy University #2 Very Good U #2 Good U #1

ID 30711. Synonym dictionary

Темы: Dictionaries

You are given a dictionary consisting of pairs of words. Each word is a synonym for its paired word. All words in the dictionary are different. For one given word, define its synonym.

Input

The program receives N number of pairs of synonyms as input. N lines follow, each line contains exactly two synonym words. This is followed by one word.

Output

The program should display a synonym for the given word.

Example

#	Input	Output
1	3 Hello Hi Bye Goodbye ListArray Goodbye	Bye

ID 37873. stitch counting words

Темы: Dictionaries

Cheerful alien Stitch is trying to settle down on our planet and learn English. So far, he can't say much, but he can already distinguish one word from another, although he may not understand them. Now Stitch is observing Leela, and for each word he hears, he says how many times it has already been said by Leela before. When Lilo gets tired of listening to Stitch mumbling, she calls him by his first name and Stitch stops. Jumba Jookiba, who became friends with Lilo and Nani, decided to test Stitch to see if he was keeping the score right. Help write a program for this.

Explanation
A word is a sequence of consecutive non-blank characters, words separated by one or more spaces or end-of-line characters.

Input
The program receives text as input. The sign of the end of the text is the word STITCH, which is located in the last line, there are no other words in the last line.

Imprint
For each word encountered in the text, display how many times it has occurred before. The word STITCH is not included in the text.

Examples

#	Input	Output
1	one two one tho three STITCH	0 0 1 0 0
2	a b a c a b a d a b a c a b a STITCH	0 0 1 0 2 1 3 0 4 2 5 1 6 3 7

ID 37876. The most important thing is family!

Темы: Dictionaries

One of the most famous quotes from the cartoon: "Ohana — it means family, in the family they will not leave anyone and they will never forget…» What else is there to add? So it is!

Lilo wants to make a family tree of her family in order to try to find as many of her relatives as possible. In the family tree, as you know, everyone except the ancestor has exactly one parent. Lilo wants to know how to position some two family members in relation to each other. Lilo's older sister Nani remembers perfectly who is the parent of whom. She is ready to help Lilo, but she has so much work to do. Help Nani write a program for Lilo.

Input
The program receives as input the number of elements in the genealogical tree N. This is followed by a \(N-1\) string that specifies the parent for each element in the tree, except for the ancestor. Each line looks like:
child_name parent_name.

Further to the end of the file there are lines containing the names of two elements of the tree.

Imprint
For each such query, print one of three numbers:
1 - if the first element is an ancestor of the second;
2 - if the second is an ancestor of the first;
0 - if neither is an ancestor of the other.

Examples

#	Input	Output
1	9 Keaka Kayla Ikika Kayla Akeneki Kayla Neolani Keaka Ley Ikika Kianalu Ley Aalona Kianalu Iukini Kianalu Ikika Iukini Neolani Kayla Keaka Kianalu END!	1 2 0

ID 37875. True friends always take care of each other

Темы: Dictionaries

Stitch is always ready to share a piece of cake with a friend, help Lilo build the best sandcastle and cook breakfast for the whole family. Take an example :)

Stitch loves to cook. The residents liked his dishes so much that they began to place orders. While cooking, Stitch mutters each order under his breath, namely the name of the dish and the quantity he needs to cook for a particular order. You need to help Stitch and sum up the results: for each dish, determine the total amount that needs to be cooked.

Input
Each line contains the name of the dish, followed by a space followed by the quantity (a natural number not exceeding 500000). The last line contains the single word "END!" - a sign of the end of input.

Imprint
Print all the dishes in lexicographical order, then, separated by a space, print the total number that Stitch needs to cook.

Examples

#	Input	Output
1	Yapper 10 Yapper 5 Clip 9 Clip 8 Yapper 1 END!	Clip 17 Yapper 16

ID 37878. Stitch is learning English

Темы: Dictionaries

Lilo and Nani teach Stitch English words. In addition to memorizing the words themselves, Stitch needs to correctly place stresses in them. Nani has a dictionary that contains all English words with their accents.
Lilo decided to train Stitch to pronounce the words correctly. But since she herself has not yet learned some words, she uses Nani's dictionary for verification. Unfortunately, not all words are present in this dictionary. Lilo decided that in words that are not in the dictionary, she will consider the stress to be correct if it is placed on only one letter.
It turned out that some words can be stressed in more than one way. In this case, the word can be pronounced differently.

Using this dictionary, check Stitch's speech for the correct placement of stress. Determine the number of mistakes Stitch will make.

Input
First enter the number N — number of words in dictionary (\(0 <= N <=20000\)).
Next comes N lines with words from the dictionary. Each word consists of no more than 30 characters. All words consist of small and capital Latin letters. Each word capitalizes exactly one letter — the one that is under stress. The words in the dictionary are in alphabetical order. If there are several possibilities for placing stress in the same word, then these options in the dictionary go in random order.

Next is a recording of Stitch's conversation. A conversation is a line of text with a total volume of no more than 300,000 characters. A string consists of words separated by exactly one space. The length of each word does not exceed 30 characters. All words consist of small and capital Latin letters (capital letters are those letters over which Stitch has put stress). Stitch could mistakenly put more than one stress in a word or not put stress at all.

Imprint
Print the number of mistakes in Stitch's speech.

Examples

#	Input	Output	Note
1	4 cAnnot cannOt found page thE pAge cAnnot be found	2	In the word cannot, according to the dictionary, there are two options for placing stress. These options in the dictionary can be listed in any order (i.e. cAnnot first, and then cannOt, and vice versa). Two mistakes made by Stitch are the words be (the emphasis is not placed at all) and fouNd (the emphasis is wrong). The word thE is not in the dictionary, but since Stitch put exactly one stress in it, it is recognized as correct.
2	4 cAnnot cannOt found page The PAGE cannot be found	4	Incorrectly placed stresses in all words, except for The (it is not in the dictionary, it has exactly one stress). In the rest of the words, either all letters are stressed (in the word PAGE), or not a single stress is set.

ID 37874. Everyone is entitled to a second chance

Темы: Dictionaries

Stitch is a genetic experiment 626 created by the evil genius Jumba Jookiba. And no matter how cute Stitch turned out at the end of the experiment, Jumbo still saw the destructive potential in him and continued to work on him. But before finishing work on Stitch, they were both detained by the Galactic Police.
Stitch was sentenced by the Supreme Councilor to life exile on a desert asteroid, but along the way he escapes and ends up on our planet on the Hawaiian island Kauai, where Lilo's love and care turned an evil alien into a kind and sympathetic friend! Jumbo Jukibo - ; an alien from the planet Kviltakuan (Kweltikwan). He was sent to Earth to capture Experiment 626. In order for the mission to take place, Jumbo had to learn English. To do this, he created an English-Quiltaqua dictionary. For every English word he encountered, Jumbo recorded a few Quiltaquan translations words into his dictionary.
Unfortunately, he realized late that he also needed a Quiltaqua-English dictionary. He decided to make a Quiltaquan-English dictionary from an English-Quiltaquan during the flight.
For each Quiltaquan word that appears in the dictionary, Jumbo wants to find all its translations (that is, all English words for which a Quiltaquan word has appeared in its list of translations) and treat them, and only them, as translations of that Quiltaquan word.
Help Jumbo complete the work of creating a Quiltaquan-English dictionary so that he can learn it by the time he arrives on our planet.

Input
The first line contains a single integer N — the number of English words in the dictionary. This is followed by N descriptions. Each description is on a separate line, with the English word first, followed by a space-separated hyphen (character number 45), then comma-and-space-separated translations of that English word into Quiltaquan. Translations are sorted in lexicographic order. The order of English words in the dictionary is also lexicographic.
All words consist only of small Latin letters, the length of each word does not exceed 15 characters. The total number of words in the input does not exceed 100,000.

Imprint
Output the corresponding Quiltaquan-English dictionary, following exactly the format of the input data. In particular, the translation of the lexicographically minimal Quiltakuan word should come first, followed by — the second in that order, and so on. Within the translation, English words must also be sorted lexicographically.

Examples

#	Input	Output
1	3 apple - malum, pomum, popula fruit - baca, bacca, popum punishment - malum, multa	7 baca-fruit bacca-fruit malum - apple, punishment multa-punishment pomum-apple popula-apple popum-fruit

ID 38117. Acowdemia II

Темы: Dictionaries

Besi goes to work in a computer lab. She wants to determine the degree of importance of each of N lab workers (1≤N≤100). All degrees of importance are different. That is, no two employees have the same degree of importance. Besi uses the list of lab publications to determine the importance of employees.

Each publication contains a list of authors, which is an ordered list of all N employees of the laboratory. The list is compiled in descending order of the contribution of each of the employees to this article. If multiple workers have made the same contribution, then they are ordered alphabetically. Because the more important worker has additional administrative responsibilities, he never contributes more than the less important worker.

For example, if the lab consists (in ascending order of importance) of a student Elsie, prof. Mildred and prof. Dean, they can be the authors of the article (Elsie-Mildred-Dean) if they all contributed a different amount of effort. Namely, Elsie contributed more effort than Mildred, and Mildred more than Dean. However, they can also have an article in the Elsie-Dean-Mildred order if Mildred and Dean contributed the same amount of effort and Elsie is greater than both of them.

Given K publications from this lab (1≤K≤100), help Besi determine for all pairs of employees in this lab who is more important, if possible.

INPUT FORMAT
The first line contains two integers K and N.
The second line contains N lines, separated by single spaces, containing the names of the lab members. Each name consists of no more than 10 small Latin letters.

Each of the following K lines contains N lines separated by single spaces, indicating the list of authors in one publication.

OUTPUT FORMAT
The output should consist of N lines, N characters per line. On line i, for any j≠i, the j-th character must be 1 if the i-th member is more important than the j-th one, 0 if the i-th member is less important than the j-th one, and ? if it is impossible to determine given the list of publications.
The i-th character in string i should be B because that's Besi's favorite character.

Examples

#	Input	Output	Explanation
1	1 3 dean elsie mildred elsie mildred dean	B11 0b? 0?B	In the first example, one article (elsie-mildred-dean) does not provide enough information to determine who is more important than elsie or mildred. However, Dean is definitely more important than both. Therefore both orders are possible Elsie<Mildred<Dean and Mildred<Elsie<Dean
2	2 3 elsie mildred dean elsie mildred dean elsie dean mildred	B00 1B0 11B	In this second example, the only possible order that satisfies both articles is Elsie<Mildred<Dean since the second posting helps determine that Mildred is more important than Elsie.

ID 38778. Air balloons

Темы: Dictionaries

The Spring Festival is coming to the Flower City. For the holiday, it was decided to inflate a large number of balloons. Each shorty got an unlimited supply of balloons. To speed up the counting of inflated balloons, Vintik and Shpuntik invented a robot that keeps count of all inflated balloons.

Each shorty, at the moment when a robot is next to him, can do one of two things.

Press button 1, say your name and say how many balloons he blew up (say a positive number) or how many balloons he burst (say a negative number). After that, the robot counts the number of inflated balloons this shorty has.
Press button 2, say the name of any shorty. After that, the robot shows on the screen the number of inflated balloons for the specified shorty. If the robot has never passed the specified shorty (didn't remember its balls), then the robot outputs the word ERROR.

Please note that in a situation where the shorty burst exactly as many balloons as he inflated, the sum of the robot becomes equal to 0; but, since the robot has already counted its balls, a zero value is not a reason to display ERROR.

At the beginning, all shorties have 0 inflated balloons. Any shorty can accidentally pop someone else's balloons. Therefore, the score of balls for any shorty can be both positive and negative.
The robot can pass any shorty any number of times.
After driving past the specified number of shorties, the robot displays the total number of inflated balloons.

Help Vintin and Shpuntik write a program for the robot. Be sure to use dictionaries (associative arrays).

Input
The program receives as input the number of requests N (1 < N < 100000) - the number of shorties that the robot must pass by. This is followed by N lines, each of which describes how to select buttons shorty.
Line formats:
- when button 1 is pressed: 1 <name> <number>;
- on button 2 click: 2 <name>.
<name> - any sequence of Latin characters.

Imprint
When button 2 is pressed, the program should display, on a new line, the current value of balloons for the specified shorty (or the word ERROR). In the last line, print the total number of inflated balloons by all shorties.

Example

#	Input	Output
1	7 1 neznayka 3 1 donut 5 2 neznayka 1 neznayka-2 2 neznayka 2 lala 2 donuts	3 1 ERROR 5 6

ID 38779. Food stock

Темы: Dictionaries

Znayka from the Flower City invented the rocket. One fine day it was decided to fly to the moon. For a successful flight, the rocket must have a certain supply of food. So that any shorty would not be sad during the flight, it was decided to ask everyone his favorite product and the number of packages that he needs for the entire flight. As a result, Znayka had a very large list in his hands, in which the names of the products were repeated with different amounts. Znayka asks you for help. He wants a list of products in lexicographical order, with the total number of packages of each product.

Input
The program receives a list of strings. Each string contains the name of the product, followed by a space followed by the number of packages that shorty indicated. The list ends with the word END!.

Imprint
Print the name of all products in lexicographic order, then, separated by a space, the total number of packages of this product.

Examples

#	Input	Output
1	cookies 10 cookies 5 syrup 9 syrup 8 cookies 1 END!	cookies 16 syrup 17

ID 38783. Food stock - 2

Темы: Dictionaries

Znayka from the Flower City invented the rocket. For the flight to the moon, it was decided to make a stock of a certain number of different products. After interviewing all the shorties, Znayka had a very large list in his hands, in which the wish of each shorty was written in the form of the name of the product and the number of packages. At the meeting, it was decided that it was not rational to take food with a total number of packages less than 50. Help the shorties determine which products do not need to be stocked. Print these products in lexicographic order (from a to z).

Input
The program receives a list of strings. Each string contains the name of the product, followed by a space followed by the number of packages that shorty indicated. The list ends with the word END!.

Imprint
Print the name of all unnecessary products in lexicographic order. Print each product on a separate line.

Examples

#	Input	Output
1	cookies 10 cookies 50 syrup 9 syrup 8 cookies 1 apples 2 END!	apples syrup

ID 38784. Nishtyachki young programmers

Темы: Dictionaries

PYTHON INFINITE TYPE?
At the summer programming training camp, for each solved problem, they were given a certain amount of fanfiction. During the shift, young programmers could spend these fanfictions on buying various goodies. At the end of the shift, the organizers accumulated a large list, each line of which is a record of the form Programmer good amount, where Programmer - name of the young programmer (string without spaces), nice item - name of the purchased item (string without spaces), number< /tt> — number of purchased units nishtyachka.

Output a generalized list, indicating the name of the young programmer and all the goodies that he acquired during the shift and their number. Input The program receives as input a set of strings in the format specified in the problem statement. Imprint Print a list of all buyers in lexicographical order, after the name of each buyer print, in parentheses, the total number of purchased goodies, then, after the colon, print a list of the names of all goodies purchased by the programmer in lexicographic order, after the name of each goody print the number of units of acquired goodies. Information about each niche is displayed on a separate line. Examples # Input Output 1 Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5 Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5

ID 38787. Object Properties - 1

Темы: Dictionaries

There are n objects in Vasya's storage, numbered from 1 to n, each of which has a certain number of properties (possibly none). Each property is represented as a natural number from 1 to 10⁹.
After analyzing the structure of his storage, Vasya decided that it should support two operations:
- Removing obsolete property c. When a property is deleted, it is deleted from all objects it belongs to.
If the specified property does not exist, there is no need to do anything.
- Find the number of remaining properties of the object with number r.
Vasya really needs to implement this functionality, and he turned to you for help. Help him - write a program that will support both operations that Vasya needs.

Input
The first line of the input file contains the number n - the number of objects in Vasya's storage (1 <= n <= 10⁵). The i-th of the next n lines contains a description of the properties of the object with number i: first, the number ki is given - the number of properties of the i-th object, and then ki numbers pi,j - the properties of the i-th object (0 < ;= k_i <= 100, 1 <= p_i,j <= 10⁹).
All objects are numbered from 1 to n in the order presented in the input. It is guaranteed that the total number of properties of all objects does not exceed 10⁵. It is also guaranteed that for each i all pi,j are distinct.
Line n + 2 contains number q - the number of requests to Vasya's storage (1 <= q <= 10⁵).
The j-th of the following q lines contains information about the j-th request:
-c if you want to remove obsolete property c from storage (1 <= c <= 10⁹);
? r if you want to find the number of remaining properties of the object with number r.

Imprint
For all requests to find the number of remaining properties of the object, on separate lines, in the order they appear for each request, print this number.

Examples

#	Input	Output
1	2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	2 3 1 2 1 1 1 1

Remark

Only the first object has property 1, so after deleting it, the first object has 2 properties, and the second still has 3.
Property 2 is present on both objects, so it is removed from both objects, leaving the first object with 1 property and the second with 2.
Only the second object has property 5, so after removing it, both objects have 1 property.
None of the objects have property 6, so deleting it does not change the number of properties for objects.

ID 38788. Object properties - 2

Темы: Dictionaries

There are n objects in Vasya's storage, numbered from 1 to n, each of which has a certain number of properties (possibly none). Each property is represented as a natural number from 1 to 10⁹.
After analyzing the structure of his storage, Vasya decided that it should support two operations:
- Removing obsolete property c. When a property is deleted, it is deleted from all the objects it belongs to. If the specified property does not exist, nothing needs to be done.
- Find the number of properties removed from an object r
Vasya really needs to implement this functionality, and he turned to you for help. Help him - write a program that will support both operations that Vasya needs.

Input
The first line of the input file contains the number n - the number of objects in Vasya's storage (1 <= n <= 10⁵). The i-th of the next n lines contains the description of the properties of the object with number i: first, the number k_i is given - the number of properties of the i-th object, and then, space-separated, k_{i< /sub> numbers pi,j - properties of the i-th object (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).

All objects are numbered from 1 to n in the order presented in the input. It is guaranteed that the total number of properties of all objects does not exceed 10⁵. It is also guaranteed that for each i all pi,j are distinct.

Line n + 2 contains number q - the number of requests to Vasya's storage (1 <= q <= 10⁵).

The j-th of the following q lines contains information about the j-th request:

-c if you want to remove obsolete property c from storage (1 <= c <= 10⁹);

? r if you want to find the number of remaining properties of the object with number r.

Imprint

For all requests to find the number of remaining properties of the object, on separate lines, in the order they appear for each request, print this number.}

Examples

#	Input	Output
1	2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	1 0 2 1 2 2 2 2

Remark

Only the first object has property 1, so after removing it, the first object has 1 property removed, while the second still has 0.
Property 2 is on both objects, so it is removed from both objects, the first object now has 2 properties removed, and the second one has 1.
Only the second object has property 5, so after removing it, both objects have 2 properties removed.
None of the objects have property 6, so deleting it does not change the number of properties removed from objects.

ID 38789. Dormitory pass - 2

Темы: Dictionaries

There is a turnstile at the entrance to the hostel. To pass through it, you need to attach a pass. The pass must be applied both at the entrance to the hostel and at the exit from it. In order to exclude unauthorized passages, the pass does not work twice in a row to enter and twice in a row to exit.

However, cunning students figured out how to get around this limitation. To enter or exit together with one pass, they apply it from the right side, then from the opposite side, but no one passes, and then again from the right one.

The head of security decided to deal with this problem and reprimand all violators. Each login/logout event has an entry in the event log. It considers those pass holders who have three events of the form exit-in-out in less than dt minutes.

You are given the turnstile event log. It is required to display a list of those students who will be reprimanded.

Input

The first line contains two numbers n and dt — the number of entries in the turnstile event log and the time limit selected by the head of security, respectively (1≤n≤1000, 3≤dt≤1440).

The following nn lines list the entries in the event log in chronological order. The log entry consists of three parts, separated by a space:

Event time in the format hh:mm
The student's last name, consisting of no more than 20 Latin letters, the first of which is capital.
Event type: in if logged in and out if logged out.

It is guaranteed that there are no two events that happen at the same time. It is also guaranteed that any two different students have different surnames and that one student does not have two events of the same type in a row.

Imprint

In the first line print the number of violators. Then print the last names of the offenders in lexicographical order.

Examples

#	Input	Output
1	6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:32 Petrov in 01:33 Ivanov out	1 Ivanov
2	6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:33 Petrov in 01:34 Ivanov out	0

ID 38790. Dormitory pass - 1

Темы: Dictionaries

There is a turnstile at the entrance to the hostel. To pass through it, you need to attach a pass. The pass must be applied both at the entrance to the hostel and at the exit from it. In order to exclude unauthorized passages, the pass does not work twice in a row for entry and two times in a row for exit.

However, cunning students figured out how to get around this limitation. To enter or exit together with one pass, they apply it from the right side, then from the opposite side, but no one passes, and then again from the right one.

The head of security decided to deal with this problem and reprimand all violators. Each login/logout event has an entry in the event log. It considers as infringers those passholders who have three login-logout-login events in less than dt minutes.

You are given the turnstile event log. It is required to display a list of those students who will be reprimanded

Input
The first line contains two numbers n and dt — the number of entries in the turnstile event log and the time limit chosen by the head of security, respectively (1≤n≤1000, 3≤dt≤1440).
The next nn lines give entries in the event log in chronological order. The log entry consists of three parts, separated by a space:

Event time in hh:mm format
Student's last name, consisting of no more than 20 letters of the Latin alphabet, the first of which is capital.
Event type: in if logged in and out if logged out.

It is guaranteed that there are no two events that happen at the same time. It is also guaranteed that any two different students have different surnames and that one student does not have two events of the same type in a row.

Imprint
In the first line print the number of offenders. Then print the last names of the offenders in lexicographical order.

Examples

#	Input	Output
1	6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:32 Petrov in 01:33 Ivanov out	1 Petrov
2	6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:33 Petrov in 01:34 Ivanov out	0

ID 38791. Submatrix - 1

Темы: Dictionaries

Fili has an N×N square matrix A, but it seems too big for him. He likes matrices of size k×k (k<N) much more.
Filya wants to get a matrix of the required size by taking some submatrix of the original matrix.
The submatrix k×k of the matrix A in this case, Filya considers the matrix B such that b_i,j=a_i+x,j+y, for all i, j from 1 to k. From this definition, you can see that the submatrix of the original matrix is given by a pair of numbers (x, y).
In order to choose the most interesting submatrix for himself, Filya wants to know how many ways there are to choose from the original matrix two different (characterizing pairs (x, y) differ at least in one position) equal submatrices k×k. Two matrices Q and P of size k×k are considered equal if for any i,j:1≤i,j≤k q_i,j=p_i,j .
If the equality condition is not met, the matrices are considered unequal.

Input
The first line of the input file contains two natural numbers N and k - the sizes of the original and required matrix.
(1<=k<=N<=10). The next N lines contain space-separated N natural numbers ai,j - elements of the original matrix (1<=a_i,j<10).

Imprint
In a single line of the output file print a single number - the number of ways to select from the original matrix two different equal submatrices of size k×k.

Examples

#	Input	Output
1	3 1 1 2 3 4 5 6 7 8 9	0
2	3 1 1 1 1 1 1 1 1 1 1	36
3	3 2 1 2 1 1 1 2 1 1 1	1

ID 38835. 3 cows

Темы: Dictionaries

Sklises — "marsupial artiodactyls" in the form of a cow with membranous wings from the planet Sheshineru. Despite the ability to fly, the Skliss, like any terrestrial cow, is quite lazy and slow-witted (read more about skliss).
Professor Igor Seleznev took on board three sklisses for study: Bessie (Bessie), Elsie (Elsie) and Mildred (Mildred), each of which initially produces 7 gallons of milk per day. Since it is known that the yield of the skliss may change over time, Professor Seleznev takes periodic measurements over the next 100 days and writes them down in a log. The entries in his journal look like this:

35 Bessie-2 14 Mildred +3

The first entry indicates that on Day 35, Bessie's milk yield was 2 gallons lower than at the last measurement. The following entry indicates that on day 14, Mildred's milk production increased by 3 gallons compared to when it was last measured.
Professor Seleznev is busy with many studies, so he can take no more than one measurement per day. Unfortunately, he does not always have time to record everything in a log at once and, therefore, his measurements may not be in chronological order.

To keep the Skliss motivated, Igor Seleznev proudly hangs a photo of the Skliss with the highest milk yield on the wall of the organized farm (if there are several such Skliss, he posts all their photos).
Determine the number of days during which Professor Igor Seleznev would need to change his photo.

Input
The first line of input contains N, the number of measurements the professor took. Each of the following N lines describes a single measurement, in the format described above: a day (an integer from 1 to 100), a Skliss name, and a performance change (a non-zero integer). The amount of milk that any skliss gives will always be in the range 0..1000.

Imprint
Print e number of days during which Professor Igor Seleznev would need to change his photo.

Examples

#	Input	Output	Explanation
1	4 7 Mildred +3 4 Elsie-1 9 Mildred-1 1 Bessie +2	3	Initially, all Sklisses yield 7. On Day 1, Bessie's performance will rise to 9, making her the only winner and forcing the Professor to change her photo. On day 4, Elsie's performance will drop to 6, but that won't change the fact that Bassie will remain the leader. On day 7, Mildred will take the lead, on day 8, Mildred will be level with Bessie, which will again lead to a change of cards.

ID 45254. Combining Like Elements

Темы: Dictionaries

Given a two-dimensional array of integers, items1 and items2, representing two sets of elements. Each of these arrays has the following properties:

items[i] = [value_i, weight_i] where value_i denotes value and weight_i denotes weight ;i^th element;
the value of each element is unique.

Return a two-dimensional array ret, where ret[i] = [value_i, weight_i]< /code>, in which weight_i is sum of weights ;all values value_i. The array ret should be sorted in ascending order by value value.






Input

The program receives as input in the first line an integer n1 - the number of elements in the array items1. Then n1 lines follow, each of which contains two integers value_i, weight_i- elements of the first array and their weights.< br />
The next line contains the integer n2, the number of elements in the array items2. Then n2 lines follow, each of which contains two integers value_i, weight_i- elements of the second array and their weights.< br />


Input data restrictions:

1 <= n1, n2 <= 1000
items1[i].len() == items2[i].len() == 2
1 <= value_i, weight_i <= 1000
Each value_i in items1 unique.
Each value_i in items2 unique.



Imprint

Output the ret  array in the required format (see example)

 

 
Examples




#
Input
Output




1

3
eleven
4 5
3 8
2
3 1
15


[[1, 6], [3, 9], [4, 5]]



2

3
eleven
3 2
2 3
3
2 1
3 2
13



[[1, 4], [2, 4], [3, 4]]