637B.md (1942B)
1 Source: https://codeforces.com/problemset/problem/637/B 2 3 B. Chat Order 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp is a big lover of killing time in social networks. A page with a chatlist in his favourite network is made so that when a message is sent to some friend, his friend's chat rises to the very top of the page. The relative order of the other chats doesn't change. If there was no chat with this friend before, then a new chat is simply inserted to the top of the list. 22 23 Assuming that the chat list is initially empty, given the sequence of Polycaprus' messages make a list of chats after all of his messages are processed. Assume that no friend wrote any message to Polycarpus. 24 25 Input 26 27 The first line contains integer *n* (1 ≤ *n* ≤ 200 000) — the number of Polycarpus' messages. Next *n* lines enlist the message recipients in the order in which the messages were sent. The name of each participant is a non-empty sequence of lowercase English letters of length at most 10. 28 29 Output 30 31 Print all the recipients to who Polycarp talked to in the order of chats with them, from top to bottom. 32 33 Examples 34 35 Input 36 37 ``` 38 4 39 alex 40 ivan 41 roman 42 ivan 43 ``` 44 45 Output 46 47 ``` 48 ivan 49 roman 50 alex 51 ``` 52 53 Input 54 55 ``` 56 8 57 alina 58 maria 59 ekaterina 60 darya 61 darya 62 ekaterina 63 maria 64 alina 65 ``` 66 67 Output 68 69 ``` 70 alina 71 maria 72 ekaterina 73 darya 74 ``` 75 76 Note 77 78 In the first test case Polycarpus first writes to friend by name "alex", and the list looks as follows: 79 80 1. alex 81 82 Then Polycarpus writes to friend by name "ivan" and the list looks as follows: 83 84 1. ivan 85 2. alex 86 87 Polycarpus writes the third message to friend by name "roman" and the list looks as follows: 88 89 1. roman 90 2. ivan 91 3. alex 92 93 Polycarpus writes the fourth message to friend by name "ivan", to who he has already sent a message, so the list of chats changes as follows: 94 95 1. ivan 96 2. roman 97 3. alex