시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 17 7 6 46.154%

문제

고고학자들은 고대 문명이 남긴 이상한 기계를 발견하였다. 이 기계는 두 정수 x와 y를 출력하는 두 부분이 있다.

이 기계를 조사해보고, 고고학자들은 이 기계가 과거의 어느 시점부터 시작하여 시점 t에 대한 정보를 출력 하는 특별한 시계라는 결론을 내렸다. 시점 T에서 첫번째 출력 부분에서는 정수 x = ((t + ⌊t/B⌋ ) mod A)를 출력하고, 두번째 출력 부분에서는 정수 y = (t mod B)를 출력한다. (⌊x⌋는 x 이하이면서 가장 큰 정수를 나타낸다.)

분석을 해 보니 이 기계가 항상 동작하는 것은 아니며, n개의 연속된 구간 [li, ri]에서만 동작하는 것을 알게 되었다. 향후 연구를 위해서, 고고학자들은 당신에게 이 기계가 출력하는 순서쌍 (x, y) 중 서로 다른 것이 모두 몇 개인지를 알아내는 프로그램을 작성하도록 부탁했다.

두 순서쌍 (x1, y1)와 (x2, y2)는 만약 x1 ≠ x2이거나 y1 ≠ y2이라면 서로 다르다.

입력

첫 줄에는 세 정수 n, A, B가 주어진다. (1 ≤ n ≤ 106; 1 ≤ A, B ≤ 1018).

다음 n줄의 각각에는 두 정수 li와 ri가 주어지는데, 이 기계가 동작하는 구간 [li, ri]의 시작 시점과 종료 시점을 나타낸다. (0 ≤ li ≤ ri ≤ 1018 , ri < li+1).

출력

이 기계가 동작하는 동안 출력하는 서로 다른 순서쌍 (x, y)의 수를 출력한다.

예제 입력 1

3 3 3
4 4
7 9
17 18

예제 출력 1

4

예제 입력 2

3 5 10
1 20
50 68
89 98

예제 출력 2

31

예제 입력 3

2 16 13
2 5
18 18

예제 출력 3

5

힌트

첫번째 테스트에서, 이 기계는 시점 4에서 (2, 1)을, 시점 7에서 (0, 1)을, 시점 8에서 (1, 2)를, 시점 9 에서 (0, 0)를, 시점 17에서 (1, 2)를, 시점 18에서 (0, 0)를 출력한다. 따라서 서로 다른 네 개의 순서쌍 (0, 0),(0, 1),(1, 2),(2, 1)을 출력한다.

W3sicHJvYmxlbV9pZCI6IjE3NjM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHVjMGMxXHVkNTVjIFx1YWUzMFx1YWNjNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YWNlMFx1YjMwMCBcdWJiMzhcdWJhODVcdWM3NzQgXHViMGE4XHVhZTM0IFx1Yzc3NFx1YzBjMVx1ZDU1YyBcdWFlMzBcdWFjYzRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM3NzQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggeFx1YzY0MCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViZDgwXHViZDg0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWM4NzBcdWMwYWNcdWQ1NzRcdWJjZjRcdWFjZTAsIFx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YWNmY1x1YWM3MFx1Yzc1OCBcdWM1YjRcdWIyOTAgXHVjMmRjXHVjODEwXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWMyZGNcdWM4MTAgdFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1Y2Q5Y1x1YjgyNSBcdWQ1NThcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1YzJkY1x1YWNjNFx1Yjc3Y1x1YjI5NCBcdWFjYjBcdWI4NjBcdWM3NDQgXHViMGI0XHViODM4XHViMmU0LiBcdWMyZGNcdWM4MTAgVFx1YzVkMFx1YzExYyBcdWNjYWJcdWJjODhcdWM5ZjggXHVjZDljXHViODI1IFx1YmQ4MFx1YmQ4NFx1YzVkMFx1YzExY1x1YjI5NCBcdWM4MTVcdWMyMTggeCA9ICgodCArICZsZmxvb3I7dFwvQiZyZmxvb3I7ICkgbW9kIEEpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHViNDUwXHViYzg4XHVjOWY4IFx1Y2Q5Y1x1YjgyNSBcdWJkODBcdWJkODRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjODE1XHVjMjE4IHkgPSAodCBtb2QgQilcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoJmxmbG9vcjt4JnJmbG9vcjtcdWIyOTQgeCBcdWM3NzRcdWQ1NThcdWM3NzRcdWJhNzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHViZDg0XHVjMTFkXHVjNzQ0IFx1ZDU3NCBcdWJjZjRcdWIyYzggXHVjNzc0IFx1YWUzMFx1YWNjNFx1YWMwMCBcdWQ1NmRcdWMwYzEgXHViM2Q5XHVjNzkxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWJhNzAsIG5cdWFjMWNcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1YWQ2Y1x1YWMwNCBbbDxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+XVx1YzVkMFx1YzExY1x1YjljYyBcdWIzZDlcdWM3OTFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1ZDVhNVx1ZDZjNCBcdWM1ZjBcdWFkNmNcdWI5N2MgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHViMmY5XHVjMmUwXHVjNWQwXHVhYzhjIFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWFjMDAgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YzMwZCAoeCwgeSkgXHVjOTExIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVhYzgzXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViM2M0XHViODVkIFx1YmQ4MFx1ZDBjMVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzIxY1x1YzExY1x1YzMwZCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KVx1YzY0MCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KVx1YjI5NCBcdWI5Y2NcdWM1N2QgeDxzdWI+MTxcL3N1Yj4gJm5lOyZuYnNwO3g8c3ViPjI8XC9zdWI+XHVjNzc0XHVhYzcwXHViMDk4IHk8c3ViPjE8XC9zdWI+ICZuZTsmbmJzcDt5PHN1Yj4yPFwvc3ViPlx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IG4sIEEsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD47IDEgJmxlOyBBLCBCICZsZTsgMTA8c3VwPjE4PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVjOTA0XHVjNzU4IFx1YWMwMVx1YWMwMVx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IGw8c3ViPmk8XC9zdWI+XHVjNjQwIHI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YWUzMFx1YWNjNFx1YWMwMCBcdWIzZDlcdWM3OTFcdWQ1NThcdWIyOTQgXHVhZDZjXHVhYzA0IFtsPHN1Yj5pPFwvc3ViPiwgcjxzdWI+aTxcL3N1Yj5dXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWMyZGNcdWM4MTBcdWFjZmMgXHVjODg1XHViOGNjIFx1YzJkY1x1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICgwICZsZTsgbDxzdWI+aTxcL3N1Yj4gJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD4xODxcL3N1cD4gLCByPHN1Yj5pPFwvc3ViPiAmbHQ7IGw8c3ViPmkrMTxcL3N1Yj4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc3NCBcdWFlMzBcdWFjYzRcdWFjMDAgXHViM2Q5XHVjNzkxXHVkNTU4XHViMjk0IFx1YjNkOVx1YzU0OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyMWNcdWMxMWNcdWMzMGQgKHgsIHkpXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMsIFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWIyOTQgXHVjMmRjXHVjODEwIDRcdWM1ZDBcdWMxMWMgKDIsIDEpXHVjNzQ0LCBcdWMyZGNcdWM4MTAgN1x1YzVkMFx1YzExYyAoMCwgMSlcdWM3NDQsIFx1YzJkY1x1YzgxMCA4XHVjNWQwXHVjMTFjICgxLCAyKVx1Yjk3YywgXHVjMmRjXHVjODEwIDkgXHVjNWQwXHVjMTFjICgwLCAwKVx1Yjk3YywgXHVjMmRjXHVjODEwIDE3XHVjNWQwXHVjMTFjICgxLCAyKVx1Yjk3YywgXHVjMmRjXHVjODEwIDE4XHVjNWQwXHVjMTFjICgwLCAwKVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjMjFjXHVjMTFjXHVjMzBkICgwLCAwKSwoMCwgMSksKDEsIDIpLCgyLCAxKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzYzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0cmFuZ2UgRGV2aWNlIiwiZGVzY3JpcHRpb24iOiI8cD5BcmNoYWVvbG9naXN0cyBoYXZlIGZvdW5kIGEgc3RyYW5nZSBkZXZpY2UgdGhhdCB3YXMgcHJvYmFibHkgY3JlYXRlZCBieSBzb21lIGFuY2llbnQgY2l2aWxpemF0aW9uLiBUaGUgZGV2aWNlIGhhcyBhIHNjcmVlbiB0aGF0IGRpc3BsYXlzIHR3byBpbnRlZ2VyczogeCBhbmQgeS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZXhwbG9yaW5nIHRoZSBkZXZpY2UgdGhlIHNjaWVudGlzdHMgaGF2ZSBtYWRlIGEgY29uY2x1c2lvbiB0aGF0IHRoZSBkZXZpY2UgaXMga2luZCBvZiBhIGNsb2NrLiBJdCBtZWFzdXJlcyB0aW1lIHQgcGFzc2VkIGZyb20gc29tZSBtb21lbnQgaW4gdGhlIHBhc3QsIGJ1dCBzaG93cyBpdCBpbiBzb21lIHdlaXJkIHdheSwgcHJvYmFibHkgdXNlZCBieSB0aGUgY3JlYXRvcnMgb2YgdGhlIGRldmljZS4gSWYgdGhlIHRpbWUgcGFzc2VkIGlzIGFuIGludGVnZXIgdCwgdGhlIHR3byBpbnRlZ2VycyBkaXNwbGF5ZWQgYXJlOiB4ID0gKCh0ICsgJmxmbG9vcjt0XC9CJnJmbG9vcjsgKSBtb2QgQSksIGFuZCB5ID0gKHQgbW9kIEIpLiBIZXJlICZsZmxvb3I7eCZyZmxvb3I7IGlzIHRoZSBmbG9vciBmdW5jdGlvbiAmbWRhc2g7IHRoZSBncmVhdGVzdCBpbnRlZ2VyIGxlc3Mgb3IgZXF1YWwgdG8geC48XC9wPlxyXG5cclxuPHA+VGhlIGFyY2hhZW9sb2dpc3RzIGhhdmUgc3R1ZGllZCB0aGUgZGV2aWNlIGFuZCBmb3VuZCBvdXQgdGhhdCBpdHMgc2NyZWVuIHdhc24mcnNxdW87dCB0dXJuZWQgb24gYWxsIHRoZSB0aW1lLiBBY3R1YWxseSBpdCB3YXMgb25seSB3b3JraW5nIGR1cmluZyBuIGNvbnRpbnVvdXMgcGVyaW9kcyBvZiB0aW1lLCB0aGUgaS10aCBvZiB0aGVtIHdhcyBmcm9tIHRoZSBtb21lbnQgbDxzdWI+aTxcL3N1Yj4gdG8gdGhlIG1vbWVudCByPHN1Yj5pPFwvc3ViPiwgaW5jbHVzaXZlLiBOb3cgdGhlIHNjaWVudGlzdHMgd291bGQgbGlrZSB0byBjYWxjdWxhdGUgaG93IG1hbnkgZGlzdGluY3QgcGFpcnMgKHgsIHkpIHdlcmUgc2hvd24gYnkgdGhlIGRldmljZSB3aGVuIGl0cyBzY3JlZW4gd2FzIG9uLjxcL3A+XHJcblxyXG48cD5Ud28gcGFpcnMgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPikgYW5kICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4pIGFyZSBkaXN0aW5jdCBpZiB4PHN1Yj4xPFwvc3ViPiAmbmU7IHg8c3ViPjI8XC9zdWI+IG9yIHk8c3ViPjE8XC9zdWI+ICZuZTsgeTxzdWI+MjxcL3N1Yj4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBuLCBBLCBhbmQgQiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD47IDEgJmxlOyBBLCBCICZsZTsgMTA8c3VwPjE4PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBsPHN1Yj5pPFwvc3ViPiBhbmQgcjxzdWI+aTxcL3N1Yj4sIHRoZSBiZWdpbm5pbmcgYW5kIHRoZSBlbmQgb2YgdGhlIGktdGggc2VnbWVudCBbbDxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+XSB3aGVuIHRoZSBkZXZpY2Ugc2NyZWVuIHdhcyB0dXJuZWQgb24gKDAgJmxlOyBsPHN1Yj5pPFwvc3ViPiAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjE4PFwvc3VwPjsgcjxzdWI+aTxcL3N1Yj4gJmx0OyBsPHN1Yj5pKzE8XC9zdWI+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBwYWlycyAoeCwgeSkgdGhhdCB3ZXJlIHNob3duIG9uIHRoZSBkZXZpY2Ugc2NyZWVuIHdoZW4gaXQgd2FzIHR1cm5lZCBvbi48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IHRlc3QsIHRoZSBkZXZpY2Ugc2NyZWVuIHNob3dzIHRoZSBmb2xsb3dpbmcgaW50ZWdlcnMuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyMCU7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+dDxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KHgsIHkpPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj40PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oMiwgMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+NzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KDAsIDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPigxLCAyKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj45PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oMCwgMCk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+MTc8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPigxLCAyKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4xODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KDAsIDApPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5TbyB0aGVyZSBhcmUgZm91ciBkaXN0aW5jdCBwYWlycyAoMCwgMCksKDAsIDEpLCgxLCAyKSwoMiwgMSkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=