시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 84 40 35 71.429%

문제

크기를 무시할 수 있는 개미 여러 마리가 줄 위를 일정한 속도 1mm/s로 걸어가고 있다.

개미가 장애물 (줄의 끝이나 다른 개미)을 만나면, 그 즉시 방향을 바꾸고 같은 속도로 계속 걸어가게 된다.

개미의 처음 위치와 방향 (왼쪽 또는 오른쪽)이 주어진다. 개미는 1번부터 N번까지 왼쪽에 있는 개미부터 차례대로 번호가 매겨져 있다. 두 개미의 처음 위치가 같은 경우는 없다.

T초가 지난 후에 모든 개미의 위치를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 줄의 길이 L과 T가 주어진다. (2 ≤ L ≤ 200,000, 1 ≤ T ≤ 1,000,000) T의 단위는 초이다.

둘째 줄에는 개미의 수 N이 주어진다. (1 ≤ N ≤ 70,000, N < L)

다음 N개 줄에는 개미의 처음 위치 (줄의 왼쪽 끝에서 떨어진 거리)와 개미가 바라보고 있는 방향이 1번 개미부터 순서대로 주어진다. 처음 위치는 정수이고, 방향은 L(왼쪽) 또는 D(오른쪽) 이다. 

출력

T초가 지난 후에 개미의 위치를 출력한다. 개미의 위치는 1번 개미부터 N번 개미까지 순서대로 출력해야 한다.

예제 입력 1

8 10
5
1 L
3 L
4 D
6 L
7 D

예제 출력 1

1 2 4 7 7
W3sicHJvYmxlbV9pZCI6IjMyMjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWI5N2MgXHViYjM0XHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzFjXHViYmY4IFx1YzVlY1x1YjdlYyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVjOTA0IFx1YzcwNFx1Yjk3YyBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVjMThkXHViM2M0IDFtbVwvc1x1Yjg1YyBcdWFjNzhcdWM1YjRcdWFjMDBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMWNcdWJiZjhcdWFjMDAgXHVjN2E1XHVjNTYwXHViYjNjIChcdWM5MDRcdWM3NTggXHViMDVkXHVjNzc0XHViMDk4IFx1YjJlNFx1Yjk3OCBcdWFjMWNcdWJiZjgpXHVjNzQ0IFx1YjljY1x1YjA5OFx1YmE3NCwgXHVhZGY4IFx1Yzk4OVx1YzJkYyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWMxOGRcdWIzYzRcdWI4NWMgXHVhY2M0XHVjMThkIFx1YWM3OFx1YzViNFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxY1x1YmJmOFx1Yzc1OCBcdWNjOThcdWM3NGMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmMyOVx1ZDVhNSAoXHVjNjdjXHVjYWJkIFx1YjYxMFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmQpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzFjXHViYmY4XHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMxY1x1YmJmOFx1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjYzk4XHVjNzRjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+VFx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5MDRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWFjZmMgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTCAmbGU7IDIwMCwwMDAsIDEgJmxlOyBUICZsZTsgMSwwMDAsMDAwKSBUXHVjNzU4IFx1YjJlOFx1YzcwNFx1YjI5NCBcdWNkMDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzFjXHViYmY4XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNzAsMDAwLCBOICZsdDsgTCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWNjOThcdWM3NGMgXHVjNzA0XHVjZTU4IChcdWM5MDRcdWM3NTggXHVjNjdjXHVjYWJkIFx1YjA1ZFx1YzVkMFx1YzExYyBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjKVx1YzY0MCBcdWFjMWNcdWJiZjhcdWFjMDAgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzQgMVx1YmM4OCBcdWFjMWNcdWJiZjhcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjYzk4XHVjNzRjIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWFjZTAsIFx1YmMyOVx1ZDVhNVx1Yzc0MCBMKFx1YzY3Y1x1Y2FiZCkgXHViNjEwXHViMjk0IEQoXHVjNjI0XHViOTc4XHVjYWJkKSBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IDFcdWJjODggXHVhYzFjXHViYmY4XHViZDgwXHVkMTMwIE5cdWJjODggXHVhYzFjXHViYmY4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMyMjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJtcmF2aSIsImRlc2NyaXB0aW9uIjoiPHA+QW50cyBvZiBuZWdsaWdpYmxlIGRpbWVuc2lvbnMgbW92ZSB3aXRoIGNvbnN0YW50IHNwZWVkIG9mIDEgbW1cL3MgYWxvbmcgdGlnaHQgYW5kIGxvbmcgd2lyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hlbiBhbiBhbnQgZW5jb3VudGVycyBhbiBvYnN0YWNsZSAoZW5kIG9mIHRoZSB3aXJlIG9yIGFub3RoZXIgYW50KSwgaXQgaW1tZWRpYXRlbHkgYm91bmNlcyBhbmQgY29udGludWVzIHRvIG1vdmUgaW4gdGhlIG9wcG9zaXRlIGRpcmVjdGlvbiB3aXRoIHRoZSBzYW1lIHNwZWVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Jbml0aWFsIHBvc2l0aW9ucyBhbmQgZGlyZWN0aW9ucyAobGVmdCBvciByaWdodCkgb2YgYW50cyBhcmUgZ2l2ZW4uIFRoZSBhbnRzIGFyZSBtYXJrZWQgYnkgbnVtYmVycyAxLCAyLCAzLCAuLi4sIE4gZnJvbSBsZWZ0IHRvIHJpZ2h0LiBObyB0d28gYW50cyBoYXZlIHRoZSBzYW1lIGluaXRpYWwgcG9zaXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBwb3NpdGlvbnMgb2YgYWxsIGFudHMgYWZ0ZXIgc29tZSBnaXZlbiB0aW1lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZmlsZSBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMsIEwgYW5kIFQsIDIgJmxlOyBMICZsZTsgMjAwLDAwMCAodGhlIGxlbmd0aCBvZiB3aXJlKSBhbmQgMSZsZTsgVCAmbGU7IDEsMDAwLDAwMCAodGltZSBpbiBzZWNvbmRzKSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgY2hhcmFjdGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29uc2lzdHMgb2YgaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDcwLDAwMCAobnVtYmVyIG9mIGFudHMpLCBOICZsdDsgTC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29uc2lzdHMgb2YgaW5pdGlhbCBwb3NpdGlvbiAodGhlIGRpc3RhbmNlIGZyb20gdGhlIGxlZnQgZW5kIG9mIHRoZSB3aXJlKSBhbmQgZGlyZWN0aW9uIG9mIGVhY2ggYW50IChmcm9tIHRoZSBhbnQgbnVtYmVyIDEgdXAgdG8gdGhlIGFudCBudW1iZXIgTikuIEluaXRpYWwgcG9zaXRpb24gaXMgZ2l2ZW4gYnkgYW4gaW50ZWdlciBhbmQgaW5pdGlhbCBkaXJlY3Rpb24gaXMgZ2l2ZW4gYnkgYSBjaGFyYWN0ZXIgJiMzOTtMJiMzOTsgKGxlZnQpIGFuZCAmIzM5O1ImIzM5OyAocmlnaHQpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IG91dHB1dCBsaW5lIHNob3VsZCBjb25zaXN0IHRoZSBmaW5hbCBwb3NpdGlvbnMgKHRoZSBkaXN0YW5jZXMgZnJvbSB0aGUgbGVmdCBlbmQgb2YgdGhlIHdpcmUpIG9mIGFsbCBhbnRzLCBzdGFydGluZyB3aXRoIHRoZSBhbnQgbWFya2VkIHdpdGggbnVtYmVyIDEgYW5kIGVuZGluZyB3aXRoIHRoZSBhbnQgbnVtYmVyIE4uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d