시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB573936615.640%

문제

강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(left), 오른쪽(right)으로 구분한다. 제일 처음에는 나룻배가 왼쪽 정박장에 위치해 있다. 이 나룻배는 한번에 최대 M명의 사람을 태울 수 있으며, 한 쪽 정박장에서 다른 쪽 정박장으로 이동하는데 양쪽 방향 모두 t만큼의 시간이 걸린다. 나룻배는 손님을 한 쪽 정박장에서 다른 쪽 정박장으로 실어 나르며 두 정박장 사이를 움직인다.

나룻배가 어떤 정박장에 도착하게 되면, 그 정박장으로 가고자 하는 사람들을 우선 모두 내려준다. 그 다음에는, 그 정박장에서 기다리고 있던 손님들을 배에 태울 수 있는 데까지 태운다. 손님이 배에 타는데 드는 시간은 없다고 가정하며, 가장 오래 기다린 사람이 먼저 배를 타게 된다. 손님을 다 태운 후에는 반대쪽 정박장으로 이동하게 된다. 만약 기다리던 손님이 없다면, 나룻배가 그 정박장에서 다음 손님을 기다리게 된다. 만약 기다리던 중 반대 쪽 정박장에 손님이 도착하면, 그 쪽 정박장으로 이동하게 된다.

각각의 손님들이 어느 정박장에 언제 도착하는지에 대한 정보가 주어질 때, 각 손님들이 원하는 곳에 도착하게 되는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 M, t, N이 주어진다. 다음 N개의 줄에는 각각의 손님이 정박장에 도착하는 시간과 도착하는 정박장의 위치가 주어진다. 손님이 정박장에 도착하는 시간은 10만 이하의 음이 아닌 정수이다.

출력

N개의 줄에, 입력받은 순서대로 각 손님이 목적지에 도착하게 되는 시간을 출력한다.

제한

  • 1 ≤ M ≤ 10,000
  • 1 ≤ t ≤ 10,000
  • 1 ≤ N ≤ 10,000

예제 입력 1

2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left

예제 출력 1

10
30
30
50
50
70
70
90
90
110

예제 입력 2

2 10 3
10 right
25 left
40 left

예제 출력 2

30
40
60
W3sicHJvYmxlbV9pZCI6IjIwNjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWI4ZmJcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxNVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWQ1NWMgXHViMzAwXHVjNzU4IFx1YjA5OFx1YjhmYlx1YmMzMFx1YWMwMCBcdWM2MjRcdWFjMDBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1XHVjNzQwIFx1YWMxNVx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgXHVjNjdjXHVjYWJkKGxlZnQpLCBcdWM2MjRcdWI5NzhcdWNhYmQocmlnaHQpXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC4gXHVjODFjXHVjNzdjIFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWIwOThcdWI4ZmJcdWJjMzBcdWFjMDAgXHVjNjdjXHVjYWJkIFx1YzgxNVx1YmMxNVx1YzdhNVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMDk4XHViOGZiXHViYzMwXHViMjk0IFx1ZDU1Y1x1YmM4OFx1YzVkMCBcdWNkNWNcdWIzMDAgTVx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1YyBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM1OTFcdWNhYmQgXHViYzI5XHVkNWE1IFx1YmFhOFx1YjQ1MCB0XHViOWNjXHVkMDdjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjA5OFx1YjhmYlx1YmMzMFx1YjI5NCBcdWMxOTBcdWIyZDhcdWM3NDQgXHVkNTVjIFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM3M2NcdWI4NWMgXHVjMmU0XHVjNWI0IFx1YjA5OFx1Yjk3NFx1YmE3MCBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1YjhmYlx1YmMzMFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVjODE1XHViYzE1XHVjN2E1XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YWRmOCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM3M2NcdWI4NWMgXHVhYzAwXHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHVjNmIwXHVjMTIwIFx1YmFhOFx1YjQ1MCBcdWIwYjRcdWI4MjRcdWM5MDBcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQsIFx1YWRmOCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDBcdWMxMWMgXHVhZTMwXHViMmU0XHViOWFjXHVhY2UwIFx1Yzc4OFx1YjM1OCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NDQgXHViYzMwXHVjNWQwIFx1ZDBkY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjM3MFx1YWU0Y1x1YzljMCBcdWQwZGNcdWM2YjRcdWIyZTQuIFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWJjMzBcdWM1ZDAgXHVkMGMwXHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjc5OCBcdWFlMzBcdWIyZTRcdWI5YjAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YmEzY1x1YzgwMCBcdWJjMzBcdWI5N2MgXHVkMGMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjMTkwXHViMmQ4XHVjNzQ0IFx1YjJlNCBcdWQwZGNcdWM2YjQgXHVkNmM0XHVjNWQwXHViMjk0IFx1YmMxOFx1YjMwMFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWUzMFx1YjJlNFx1YjlhY1x1YjM1OCBcdWMxOTBcdWIyZDhcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWIwOThcdWI4ZmJcdWJjMzBcdWFjMDAgXHVhZGY4IFx1YzgxNVx1YmMxNVx1YzdhNVx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NGMgXHVjMTkwXHViMmQ4XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjlhY1x1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFlMzBcdWIyZTRcdWI5YWNcdWIzNTggXHVjOTExIFx1YmMxOFx1YjMwMCBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNWQwIFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWIzYzRcdWNjMjlcdWQ1NThcdWJhNzQsIFx1YWRmOCBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NzQgXHVjNWI0XHViMjkwIFx1YzgxNVx1YmMxNVx1YzdhNVx1YzVkMCBcdWM1YjhcdWM4MWMgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0XHVjOWMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVhYzAxIFx1YzE5MFx1YjJkOFx1YjRlNFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhY2YzXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IE0sIHQsIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxMFx1YjljYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAsIFx1Yzc4NVx1YjgyNVx1YmMxYlx1Yzc0MCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhYzAxIFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWJhYTlcdWM4MDFcdWM5YzBcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDEwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgdCAmbGU7IDEwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjA2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZlcnJ5IExvYWRpbmcgSUlJIiwiZGVzY3JpcHRpb24iOiI8cD5CZWZvcmUgYnJpZGdlcyB3ZXJlIGNvbW1vbiwgZmVycmllcyB3ZXJlIHVzZWQgdG8gdHJhbnNwb3J0IGNhcnMgYWNyb3NzIHJpdmVycy4gUml2ZXIgZmVycmllcywgdW5saWtlIHRoZWlyIGxhcmdlciBjb3VzaW5zLCBydW4gb24gYSBndWlkZSBsaW5lIGFuZCBhcmUgcG93ZXJlZCBieSB0aGUgcml2ZXImIzM5O3MgY3VycmVudC4gQ2FycyBkcml2ZSBvbnRvIHRoZSBmZXJyeSBmcm9tIG9uZSBlbmQsIHRoZSBmZXJyeSBjcm9zc2VzIHRoZSByaXZlciwgYW5kIHRoZSBjYXJzIGV4aXQgZnJvbSB0aGUgb3RoZXIgZW5kIG9mIHRoZSBmZXJyeS48XC9wPlxyXG5cclxuPHA+VGhlcmUgaXMgYSBmZXJyeSBhY3Jvc3MgdGhlIHJpdmVyIHRoYXQgY2FuIHRha2UgbiBjYXJzIGFjcm9zcyB0aGUgcml2ZXIgaW4gdCBtaW51dGVzIGFuZCByZXR1cm4gaW4gdCBtaW51dGVzLiBBIGNhciBtYXkgYXJyaXZlIGF0IGVpdGhlciByaXZlciBiYW5rIHRvIGJlIHRyYW5zcG9ydGVkIGJ5IHRoZSBmZXJyeSB0byB0aGUgb3Bwb3NpdGUgYmFuay4gVGhlIGZlcnJ5IHRyYXZlbHMgY29udGludW91c2x5IGJhY2sgYW5kIGZvcnRoIGJldHdlZW4gdGhlIGJhbmtzIHNvIGxvbmcgaXQgaXMgY2FycnlpbmcgYSBjYXIgb3IgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIGNhciB3YWl0aW5nIGF0IGVpdGhlciBiYW5rLiBXaGVuZXZlciB0aGUgZmVycnkgYXJyaXZlcyBhdCBvbmUgb2YgdGhlIGJhbmtzLCBpdCB1bmxvYWRzIGl0cyBjYXJnbyBhbmQgbG9hZHMgdXAgdG8gbiBjYXJzIHRoYXQgYXJlIHdhaXRpbmcgdG8gY3Jvc3MuIElmIHRoZXJlIGFyZSBtb3JlIHRoYW4gbiwgdGhvc2UgdGhhdCBoYXZlIGJlZW4gd2FpdGluZyB0aGUgbG9uZ2VzdCBhcmUgbG9hZGVkLiBJZiB0aGVyZSBhcmUgbm8gY2FycyB3YWl0aW5nIG9uIGVpdGhlciBiYW5rLCB0aGUgZmVycnkgd2FpdHMgdW50aWwgb25lIGFycml2ZXMsIGxvYWRzIGl0IChpZiBpdCBhcnJpdmVzIG9uIHRoZSBzYW1lIGJhbmsgb2YgdGhlIGZlcnJ5KSwgYW5kIGNyb3NzZXMgdGhlIHJpdmVyLiBBdCB3aGF0IHRpbWUgZG9lcyBlYWNoIGNhciByZWFjaCB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgcml2ZXI/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBjLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGJlZ2lucyB3aXRoIG4sIHQsIG0uIG0gbGluZXMgZm9sbG93LCBlYWNoIGdpdmluZyB0aGUgYXJyaXZhbCB0aW1lIGZvciBhIGNhciAoaW4gbWludXRlcyBzaW5jZSB0aGUgYmVnaW5uaW5nIG9mIHRoZSBkYXkpLCBhbmQgdGhlIGJhbmsgYXQgd2hpY2ggdGhlIGNhciBhcnJpdmVzICgmcXVvdDtsZWZ0JnF1b3Q7IG9yICZxdW90O3JpZ2h0JnF1b3Q7KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgcGVyIGNhciwgaW4gdGhlIHNhbWUgb3JkZXIgYXMgdGhlIGlucHV0LCBnaXZpbmcgdGhlIHRpbWUgYXQgd2hpY2ggdGhhdCBjYXIgaXMgdW5sb2FkZWQgYXQgdGhlIG9wcG9zaXRlIGJhbmsuIE91dHB1dCBhbiBlbXB0eSBsaW5lIGJldHdlZW4gY2FzZXMuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgMCAmbHQ7IG4sIHQsIG0gJmxlOyAxMDAwMC4gVGhlIGFycml2YWwgdGltZXMgZm9yIGVhY2ggdGVzdCBjYXNlIGFyZSBzdHJpY3RseSBpbmNyZWFzaW5nLiBUaGUgZmVycnkgaXMgaW5pdGlhbGx5IG9uIHRoZSBsZWZ0IGJhbmsuIExvYWRpbmcgYW5kIHVubG9hZGluZyB0aW1lIG1heSBiZSBjb25zaWRlcmVkIHRvIGJlIDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=