The DMOJ Driveway

View as PDF

Submit solution

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

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

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 consist of lowercase, uppercase English letters and numbers.

Output Specification

Output the car's names in order starting from the most inner car that is still in the 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


Sample Explanation

The names are the cars in the driveway, as 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


There are no comments at the moment.