시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 95 15 12 17.391%

문제

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

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

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

입력

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

출력

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

예제 입력 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
W3sicHJvYmxlbV9pZCI6IjIwNjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWI4ZmJcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxNVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWQ1NWMgXHViMzAwXHVjNzU4IFx1YjA5OFx1YjhmYlx1YmMzMFx1YWMwMCBcdWM2MjRcdWFjMDBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1XHVjNzQwIFx1YWMxNVx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgXHVjNjdjXHVjYWJkKGxlZnQpLCBcdWM2MjRcdWI5NzhcdWNhYmQocmlnaHQpXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC4gXHVjODFjXHVjNzdjIFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWIwOThcdWI4ZmJcdWJjMzBcdWFjMDAgXHVjNjdjXHVjYWJkIFx1YzgxNVx1YmMxNVx1YzdhNVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMDk4XHViOGZiXHViYzMwXHViMjk0IFx1ZDU1Y1x1YmM4OFx1YzVkMCBcdWNkNWNcdWIzMDAgTSgxJmxlO00mbGU7MTAsMDAwKVx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1YyBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWNhYmQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM1OTFcdWNhYmQgXHViYzI5XHVkNWE1IFx1YmFhOFx1YjQ1MCB0KDEmbGU7dCZsZTsxMCwwMDApXHViOWNjXHVkMDdjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjA5OFx1YjhmYlx1YmMzMFx1YjI5NCBcdWMxOTBcdWIyZDhcdWM3NDQgXHVkNTVjIFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM3M2NcdWI4NWMgXHVjMmU0XHVjNWI0IFx1YjA5OFx1Yjk3NFx1YmE3MCBcdWI0NTAgXHVjODE1XHViYzE1XHVjN2E1IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuPFwvcD5cclxuPHA+XHViMDk4XHViOGZiXHViYzMwXHVhYzAwIFx1YzViNFx1YjVhNCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVhZGY4IFx1YzgxNVx1YmMxNVx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWM2YjBcdWMxMjAgXHViYWE4XHViNDUwIFx1YjBiNFx1YjgyNFx1YzkwMFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCwgXHVhZGY4IFx1YzgxNVx1YmMxNVx1YzdhNVx1YzVkMFx1YzExYyBcdWFlMzBcdWIyZTRcdWI5YWNcdWFjZTAgXHVjNzg4XHViMzU4IFx1YzE5MFx1YjJkOFx1YjRlNFx1Yzc0NCBcdWJjMzBcdWM1ZDAgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMzcwXHVhZTRjXHVjOWMwIFx1ZDBkY1x1YzZiNFx1YjJlNC4gXHVjMTkwXHViMmQ4XHVjNzc0IFx1YmMzMFx1YzVkMCBcdWQwYzBcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHViYTcwLCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViNzk4IFx1YWUzMFx1YjJlNFx1YjliMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYTNjXHVjODAwIFx1YmMzMFx1Yjk3YyBcdWQwYzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWMxOTBcdWIyZDhcdWM3NDQgXHViMmU0IFx1ZDBkY1x1YzZiNCBcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViYzE4XHViMzAwXHVjYWJkIFx1YzgxNVx1YmMxNVx1YzdhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZTMwXHViMmU0XHViOWFjXHViMzU4IFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1YjA5OFx1YjhmYlx1YmMzMFx1YWMwMCBcdWFkZjggXHVjODE1XHViYzE1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yzc0YyBcdWMxOTBcdWIyZDhcdWM3NDQgXHVhZTMwXHViMmU0XHViOWFjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWUzMFx1YjJlNFx1YjlhY1x1YjM1OCBcdWM5MTEgXHViYzE4XHViMzAwIFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHVjMTkwXHViMmQ4XHVjNzc0IFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3NCwgXHVhZGY4IFx1Y2FiZCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjMTkwXHViMmQ4XHViNGU0XHVjNzc0IFx1YzViNFx1YjI5MCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHVjNWI4XHVjODFjIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NFx1YzljMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YWMwMSBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWFjOGMgXHViNDE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IE0sIHQsIE4oMSZsZTtOJmxlOzEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5OXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCwgXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDEgXHVjMTkwXHViMmQ4XHVjNzc0IFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWFjOGMgXHViNDE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMDY1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmVycnkgTG9hZGluZyBJSUkiLCJkZXNjcmlwdGlvbiI6IjxwPkJlZm9yZSBicmlkZ2VzIHdlcmUgY29tbW9uLCBmZXJyaWVzIHdlcmUgdXNlZCB0byB0cmFuc3BvcnQgY2FycyBhY3Jvc3Mgcml2ZXJzLiBSaXZlciBmZXJyaWVzLCB1bmxpa2UgdGhlaXIgbGFyZ2VyIGNvdXNpbnMsIHJ1biBvbiBhIGd1aWRlIGxpbmUgYW5kIGFyZSBwb3dlcmVkIGJ5IHRoZSByaXZlciYjMzk7cyBjdXJyZW50LiBDYXJzIGRyaXZlIG9udG8gdGhlIGZlcnJ5IGZyb20gb25lIGVuZCwgdGhlIGZlcnJ5IGNyb3NzZXMgdGhlIHJpdmVyLCBhbmQgdGhlIGNhcnMgZXhpdCBmcm9tIHRoZSBvdGhlciBlbmQgb2YgdGhlIGZlcnJ5LjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBhIGZlcnJ5IGFjcm9zcyB0aGUgcml2ZXIgdGhhdCBjYW4gdGFrZSBuIGNhcnMgYWNyb3NzIHRoZSByaXZlciBpbiB0IG1pbnV0ZXMgYW5kIHJldHVybiBpbiB0IG1pbnV0ZXMuIEEgY2FyIG1heSBhcnJpdmUgYXQgZWl0aGVyIHJpdmVyIGJhbmsgdG8gYmUgdHJhbnNwb3J0ZWQgYnkgdGhlIGZlcnJ5IHRvIHRoZSBvcHBvc2l0ZSBiYW5rLiBUaGUgZmVycnkgdHJhdmVscyBjb250aW51b3VzbHkgYmFjayBhbmQgZm9ydGggYmV0d2VlbiB0aGUgYmFua3Mgc28gbG9uZyBpdCBpcyBjYXJyeWluZyBhIGNhciBvciB0aGVyZSBpcyBhdCBsZWFzdCBvbmUgY2FyIHdhaXRpbmcgYXQgZWl0aGVyIGJhbmsuIFdoZW5ldmVyIHRoZSBmZXJyeSBhcnJpdmVzIGF0IG9uZSBvZiB0aGUgYmFua3MsIGl0IHVubG9hZHMgaXRzIGNhcmdvIGFuZCBsb2FkcyB1cCB0byBuIGNhcnMgdGhhdCBhcmUgd2FpdGluZyB0byBjcm9zcy4gSWYgdGhlcmUgYXJlIG1vcmUgdGhhbiBuLCB0aG9zZSB0aGF0IGhhdmUgYmVlbiB3YWl0aW5nIHRoZSBsb25nZXN0IGFyZSBsb2FkZWQuIElmIHRoZXJlIGFyZSBubyBjYXJzIHdhaXRpbmcgb24gZWl0aGVyIGJhbmssIHRoZSBmZXJyeSB3YWl0cyB1bnRpbCBvbmUgYXJyaXZlcywgbG9hZHMgaXQgKGlmIGl0IGFycml2ZXMgb24gdGhlIHNhbWUgYmFuayBvZiB0aGUgZmVycnkpLCBhbmQgY3Jvc3NlcyB0aGUgcml2ZXIuIEF0IHdoYXQgdGltZSBkb2VzIGVhY2ggY2FyIHJlYWNoIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByaXZlcj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGMsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggbiwgdCwgbS4gbSBsaW5lcyBmb2xsb3csIGVhY2ggZ2l2aW5nIHRoZSBhcnJpdmFsIHRpbWUgZm9yIGEgY2FyIChpbiBtaW51dGVzIHNpbmNlIHRoZSBiZWdpbm5pbmcgb2YgdGhlIGRheSksIGFuZCB0aGUgYmFuayBhdCB3aGljaCB0aGUgY2FyIGFycml2ZXMgKCZxdW90O2xlZnQmcXVvdDsgb3IgJnF1b3Q7cmlnaHQmcXVvdDspLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBwZXIgY2FyLCBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgaW5wdXQsIGdpdmluZyB0aGUgdGltZSBhdCB3aGljaCB0aGF0IGNhciBpcyB1bmxvYWRlZCBhdCB0aGUgb3Bwb3NpdGUgYmFuay4gT3V0cHV0IGFuIGVtcHR5IGxpbmUgYmV0d2VlbiBjYXNlcy48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhhdCAwICZsdDsgbiwgdCwgbSAmbGU7IDEwMDAwLiBUaGUgYXJyaXZhbCB0aW1lcyBmb3IgZWFjaCB0ZXN0IGNhc2UgYXJlIHN0cmljdGx5IGluY3JlYXNpbmcuIFRoZSBmZXJyeSBpcyBpbml0aWFsbHkgb24gdGhlIGxlZnQgYmFuay4gTG9hZGluZyBhbmQgdW5sb2FkaW5nIHRpbWUgbWF5IGJlIGNvbnNpZGVyZWQgdG8gYmUgMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d