The DMOJ Driveway

View as PDF

Submit solution


Points: 5
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

Rimuru is working very hard for his senpai, Kirito. Rimuru goes home, in his brand new car, named Rimuru. Everyone on DMOJ parks in this driveway, and with car names respective to the names of their username in DMOJ.

Kirito tells his khouhai Rimuru to help him create a schedule of when someone goes out, or comes in. This driveway only allows the cars to come in from the entrance, and for them to come out, they have to go from the path that they came in from, assuming there are no cars blocking the way. Except, Rimuru can magically allow up to M cars from the front of the driveway to leave, so if X is going out and X is the front car and M \ge 1, X is allowed to leave. This means that each time someone leaves from the front of the driveway, M gets subtracted by 1.

Each day, there will be one action, either a car coming in or out. Kirito now wants to know the cars that are still in the strip of land after T days.

Input Specifications

Two integers, T (1 \le T \le 10^5) and M (1 \le M \le 10^3).

Next T lines: 2 space separated Strings X and C. The name of the person's car that's being parked and whether they are leaving the driveway or not.

C will always be either in or out, and X will always be consisted of lowercase, uppercase English letters and numbers.

Output Specifications

Output the car's names in order starting from the most inner car that are still in driveway after T days, each on a separate line.

Sample Input

8 2
Xyene in
quantum in
magicalsoup in
bruce in
magicalsoup out
Xyene out
quantum out
quantum in

Sample Output

magicalsoup
bruce
quantum

Sample Explanation

The names are the cars in the driveway, they come in from the right.

Day Cars in Driveway
1 Xyene
2 Xyene, quantum
3 Xyene, quantum, magicalsoup
4 Xyene, quantum, magicalsoup, bruce
5 Xyene, quantum, magicalsoup, bruce
6 quantum, magicalsoup, bruce
7 magicalsoup, bruce
8 magicalsoup, bruce, quantum

Comments

There are no comments at the moment.