시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB69611180401350526.629%

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

예제 입력 1

3
10 12 3 9
10 12 7 2
13 11 5 6

예제 출력 1

33
-1
83
W3sicHJvYmxlbV9pZCI6IjYwNjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkNWNcdWFkZmNcdWM1ZDAgSUNQQyBcdWQwZDBcdWMwYWNcdWIzMDBcdWIyOTQgXHViMGE4XHVjNTQ0XHViYTU0XHViOWFjXHVjZTc0XHVjNzU4IFx1Yzc4OVx1Y2U3NCBcdWM4MWNcdWFkNmRcdWM3NzQgXHViMTgwXHViNzdjXHVjNmI0IFx1YmIzOFx1YmE4NVx1Yzc0NCBcdWM5YzBcdWIyY2MgXHVjZTc0XHVjNzg5IFx1YzgxY1x1YWQ2ZFx1Yzc0NCBcdWQxYTBcdWIzMDBcdWI4NWMgXHVkNTU4XHVjNWVjIFx1YzEzOFx1YzZjY1x1Yzg0Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWNlNzRcdWM3ODkgXHVjODFjXHVhZDZkXHVjNzU4IFx1YmMzMVx1YzEzMVx1YjRlNFx1Yzc0MCBcdWQyYjlcdWM3NzRcdWQ1NWMgXHViMmVjXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIE1cdWFjZmMgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IHgsIHlcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWMwMSBcdWIxNDRcdWIzYzRcdWI5N2MgJmx0O3g6eSZndDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHVjMTM4XHVjMGMxXHVjNzU4IFx1YzJkY1x1Y2QwOFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgJmx0OzE6MSZndDtcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyAmbHQ7MjoyJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWM2MDBcdWIyZTQuICZsdDt4OnkmZ3Q7XHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWQ1NzRcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTVjIFx1YWM4M1x1Yzc0NCAmbHQ7eCYjMzk7OnkmIzM5OyZndDtcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWI5Y2NcdWM3N2MgeCAmbHQ7IE0gXHVjNzc0XHViYTc0IHgmIzM5OyA9IHggKyAxXHVjNzc0XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IHgmIzM5OyA9IDFcdWM3NzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHVjNzdjIHkgJmx0OyBOXHVjNzc0XHViYTc0IHkmIzM5OyA9IHkgKyAxXHVjNzc0XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IHkmIzM5OyA9IDFcdWM3NzRcdWIyZTQuICZsdDtNOk4mZ3Q7XHVjNzQwIFx1YWRmOFx1YjRlNCBcdWIyZWNcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1ZDU3NFx1Yjg1Y1x1YzExYywgXHVjNzc0IFx1ZDU3NFx1YzVkMCBcdWMxMzhcdWMwYzFcdWM3NTggXHVjODg1XHViOWQwXHVjNzc0IFx1YjNjNFx1Yjc5OFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM2MDhcdWM1YjhcdWM3NzQgXHVjODA0XHVkNTc0IFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTSA9IDEwIFx1Yzc3NFx1YWNlMCBOID0gMTJcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU3NFx1YjI5NCAmbHQ7MToxJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWFjZTAsIDExXHViYzg4XHVjOWY4IFx1ZDU3NFx1YjI5NCAmbHQ7MToxMSZndDtcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiAmbHQ7MzoxJmd0O1x1Yzc0MCAxM1x1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCAmbHQ7MTA6MTImZ3Q7XHViMjk0IFx1YjljOFx1YzljMFx1YjljOVx1Yzc3OCA2MFx1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIxMjQgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBNLCBOLCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgJmx0O006TiZndDtcdWM3NzQgXHVjZTc0XHVjNzg5IFx1YjJlY1x1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCAmbHQ7eDp5Jmd0O1x1YjI5NCBcdWJhODcgXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgVFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IE0sIE4sIHhcdWM2NDAgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSwgTiAmbGU7IDQwLDAwMCwgMSAmbGU7IHggJmxlOyBNLCAxICZsZTsgeSAmbGU7IE4pIFx1YzVlY1x1YWUzMFx1YzExYyAmbHQ7TTpOJmd0O1x1Yzc0MCBcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDAgXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM4MTVcdWMyMTgga1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIGtcdWIyOTQgJmx0O3g6eSZndDtcdWFjMDAga1x1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjljY1x1Yzc3YyAmbHQ7eDp5Jmd0O1x1YzVkMCBcdWM3NThcdWQ1NzQgXHVkNDVjXHVkNjA0XHViNDE4XHViMjk0IFx1ZDU3NFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1Yzk4OSwgJmx0O3g6eSZndDtcdWFjMDAgXHVjNzIwXHVkNmE4XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQ0NWNcdWQ2MDRcdWM3NzRcdWJhNzQsIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2MDY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FpbiBDYWxlbmRhciIsImRlc2NyaXB0aW9uIjoiPHA+SXQgd2FzIHJlY2VudGx5IHJldmVhbGVkIGJ5IHRoZSBJQ1BDIGV4Y2F2YXRpb24gdGVhbSB0aGF0IHRoZSBJbmNhIEVtcGlyZSB3YXMgZXN0YWJsaXNoZWQganVzdCBhZnRlciB0aGUgQ2FpbiBFbXBpcmUgd2hpY2ggd2FzIGEgc3BsZW5kaWQgY2l2aWxpemF0aW9uIHRoYXQgZmxvdXJpc2hlZCBpbiBTb3V0aCBBbWVyaWNhLiBJdCBpcyBiZWxpZXZlZCB0aGF0IHRoZSBwZW9wbGUgaW4gdGhlIENhaW4gRW1waXJlIHVzZWQgYW4gaW50ZXJlc3Rpbmcgb2RkIGNhbGVuZGFyLiBJbiB0aGVpciBjYWxlbmRhciwgYSB5ZWFyIHdhcyByZXByZXNlbnRlZCBieSAmbHQ7eDp5Jmd0Oywgd2hlcmUgeCBhbmQgeSBhcmUgbmF0dXJhbCBudW1iZXJzIHdoaWNoIGFyZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gTSBhbmQgTiwgcmVzcGVjdGl2ZWx5LiBUaGUgZmlyc3QgeWVhciwgdGhhdCBpcywgdGhlIGJlZ2lubmluZyBvZiB0aGUgd29ybGQgaXMgcmVwcmVzZW50ZWQgYnkgJmx0OzE6MSZndDsuIFRoZSBzZWNvbmQgeWVhciBpcyByZXByZXNlbnRlZCBieSAmbHQ7MjoyJmd0Oy4gTGV0ICZsdDt4JiMzOTs6eSYjMzk7Jmd0O2JlIHRoZSBmb2xsb3dpbmcgeWVhciBvZiAmbHQ7eDp5Jmd0Oy4gSWYgeCAmbHQ7IE0sIHgmIzM5OyA9IHggKyAxLCBvdGhlcndpc2UgeCYjMzk7ID0gMS4gU2ltaWxhcmx5LCBpZiB5ICZsdDsgTiwgeSYjMzk7ID0geSArIDEsIG90aGVyd2lzZSB5JiMzOTsgPSAxLiBUaGUgbGFzdCB5ZWFyIG9mIHRoZWlyIGNhbGVuZGFyIGlzICZsdDtNOk4mZ3Q7LiBJdCBpcyBzYWlkIHRoYXQgdGhlcmUgd2FzIGEgcHJvcGhlY3kgd2hpY2ggc3RhdGVzIHRoZSB3b3JsZCBlbmRzIGluIHRoZSB5ZWFyICZsdDtNOk4mZ3Q7LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYXNzdW1lIHRoYXQgTSA9IDEwIGFuZCBOID0gMTIuIFRoZSBmaXJzdCB5ZWFyIGlzIHJlcHJlc2VudGVkIGJ5ICZsdDsxOjEmZ3Q7LiBUaGUgeWVhciAmbHQ7MToxMSZndDsgcmVwcmVzZW50cyB0aGUgMTE8c3VwPnRoPFwvc3VwPiB5ZWFyLCAmbHQ7MzoxJmd0OyByZXByZXNlbnRzIHRoZSAxMzxzdXA+dGg8XC9zdXA+IHllYXIsIGFuZCAmbHQ7MTA6MTImZ3Q7IHJlcHJlc2VudHMgdGhlIDYwPHN1cD50aDxcL3N1cD4geWVhciB3aGljaCBpcyB0aGUgbGFzdCB5ZWFyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBmb3VyIGludGVnZXJzIE0sIE4sIHgsIGFuZCB5LCB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyB0aGUgbnVtYmVyIGsgc3VjaCB0aGF0ICZsdDt4OnkmZ3Q7IHJlcHJlc2VudHMgdGhlIGs8c3VwPnRoPFwvc3VwPiB5ZWFyLCB3aGVyZSAmbHQ7eDp5Jmd0OyBpcyB0aGUgbGFzdCB5ZWFyIG9mIHRoZSB3b3JsZCBpbiB0aGUgQ2FpbiBDYWxlbmRhci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGZvdXIgaW50ZWdlcnMgTSwgTiwgeCwgYW5kIHkgKDEgJmxlOyBNLE4gJmxlOyA0MCAwMDAsIDEgJmxlOyB4ICZsZTsgTSwgMSAmbGU7IHkgJmxlOyBOKSwgd2hlcmUgJmx0O006TiZndDsgaXMgdGhlIGxhc3QgeWVhciBvZiB0aGUgd29ybGQgaW4gdGhlIENhaW4gQ2FsZW5kYXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIGFuIGludGVnZXIgaywgd2hlcmUgdGhlIGs8c3VwPnRoPFwvc3VwPiB5ZWFyIGlzIHJlcHJlc2VudGVkIGJ5ICZsdDt4OnkmZ3Q7IGZvciB4IGFuZCB5IGdpdmVuIGluIHRoZSBpbnB1dC4gSWYgdGhlcmUgZG9lc24mcnNxdW87dCBleGlzdCBhIHllYXIgcmVwcmVzZW50ZWQgYnkgJmx0O3g6eSZndDssIHByaW50IC0xLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 B번