시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 332 58 40 16.598%

문제

강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IE0sIHQsIE4oMSZsZTtOJmxlOzEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWM4MTVcdWJjMTVcdWM3YTVcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVjODE1XHViYzE1XHVjN2E1XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5OXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCwgXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDEgXHVjMTkwXHViMmQ4XHVjNzc0IFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWFjOGMgXHViNDE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwNjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGZXJyeSBMb2FkaW5nIElJSSIsImRlc2NyaXB0aW9uIjoiPHA+QmVmb3JlIGJyaWRnZXMgd2VyZSBjb21tb24sIGZlcnJpZXMgd2VyZSB1c2VkIHRvIHRyYW5zcG9ydCBjYXJzIGFjcm9zcyByaXZlcnMuIFJpdmVyIGZlcnJpZXMsIHVubGlrZSB0aGVpciBsYXJnZXIgY291c2lucywgcnVuIG9uIGEgZ3VpZGUgbGluZSBhbmQgYXJlIHBvd2VyZWQgYnkgdGhlIHJpdmVyJiMzOTtzIGN1cnJlbnQuIENhcnMgZHJpdmUgb250byB0aGUgZmVycnkgZnJvbSBvbmUgZW5kLCB0aGUgZmVycnkgY3Jvc3NlcyB0aGUgcml2ZXIsIGFuZCB0aGUgY2FycyBleGl0IGZyb20gdGhlIG90aGVyIGVuZCBvZiB0aGUgZmVycnkuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgZmVycnkgYWNyb3NzIHRoZSByaXZlciB0aGF0IGNhbiB0YWtlIG4gY2FycyBhY3Jvc3MgdGhlIHJpdmVyIGluIHQgbWludXRlcyBhbmQgcmV0dXJuIGluIHQgbWludXRlcy4gQSBjYXIgbWF5IGFycml2ZSBhdCBlaXRoZXIgcml2ZXIgYmFuayB0byBiZSB0cmFuc3BvcnRlZCBieSB0aGUgZmVycnkgdG8gdGhlIG9wcG9zaXRlIGJhbmsuIFRoZSBmZXJyeSB0cmF2ZWxzIGNvbnRpbnVvdXNseSBiYWNrIGFuZCBmb3J0aCBiZXR3ZWVuIHRoZSBiYW5rcyBzbyBsb25nIGl0IGlzIGNhcnJ5aW5nIGEgY2FyIG9yIHRoZXJlIGlzIGF0IGxlYXN0IG9uZSBjYXIgd2FpdGluZyBhdCBlaXRoZXIgYmFuay4gV2hlbmV2ZXIgdGhlIGZlcnJ5IGFycml2ZXMgYXQgb25lIG9mIHRoZSBiYW5rcywgaXQgdW5sb2FkcyBpdHMgY2FyZ28gYW5kIGxvYWRzIHVwIHRvIG4gY2FycyB0aGF0IGFyZSB3YWl0aW5nIHRvIGNyb3NzLiBJZiB0aGVyZSBhcmUgbW9yZSB0aGFuIG4sIHRob3NlIHRoYXQgaGF2ZSBiZWVuIHdhaXRpbmcgdGhlIGxvbmdlc3QgYXJlIGxvYWRlZC4gSWYgdGhlcmUgYXJlIG5vIGNhcnMgd2FpdGluZyBvbiBlaXRoZXIgYmFuaywgdGhlIGZlcnJ5IHdhaXRzIHVudGlsIG9uZSBhcnJpdmVzLCBsb2FkcyBpdCAoaWYgaXQgYXJyaXZlcyBvbiB0aGUgc2FtZSBiYW5rIG9mIHRoZSBmZXJyeSksIGFuZCBjcm9zc2VzIHRoZSByaXZlci4gQXQgd2hhdCB0aW1lIGRvZXMgZWFjaCBjYXIgcmVhY2ggdGhlIG90aGVyIHNpZGUgb2YgdGhlIHJpdmVyPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYywgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBuLCB0LCBtLiBtIGxpbmVzIGZvbGxvdywgZWFjaCBnaXZpbmcgdGhlIGFycml2YWwgdGltZSBmb3IgYSBjYXIgKGluIG1pbnV0ZXMgc2luY2UgdGhlIGJlZ2lubmluZyBvZiB0aGUgZGF5KSwgYW5kIHRoZSBiYW5rIGF0IHdoaWNoIHRoZSBjYXIgYXJyaXZlcyAoJnF1b3Q7bGVmdCZxdW90OyBvciAmcXVvdDtyaWdodCZxdW90OykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIHBlciBjYXIsIGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBpbnB1dCwgZ2l2aW5nIHRoZSB0aW1lIGF0IHdoaWNoIHRoYXQgY2FyIGlzIHVubG9hZGVkIGF0IHRoZSBvcHBvc2l0ZSBiYW5rLiBPdXRwdXQgYW4gZW1wdHkgbGluZSBiZXR3ZWVuIGNhc2VzLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IDAgJmx0OyBuLCB0LCBtICZsZTsgMTAwMDAuIFRoZSBhcnJpdmFsIHRpbWVzIGZvciBlYWNoIHRlc3QgY2FzZSBhcmUgc3RyaWN0bHkgaW5jcmVhc2luZy4gVGhlIGZlcnJ5IGlzIGluaXRpYWxseSBvbiB0aGUgbGVmdCBiYW5rLiBMb2FkaW5nIGFuZCB1bmxvYWRpbmcgdGltZSBtYXkgYmUgY29uc2lkZXJlZCB0byBiZSAwLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==