시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 33 7 3 15.000%

문제

서기 2042년. 인터넷은 가상 현실을 만들 정도로 발전했고 사이버 범죄는 매일 일어난다. 그래서 2041년 SWERC 대회 우승자는 사이버 범죄가 일어날 때마다 도넛을 떨어뜨리는 요원을 개발해냈다. 모든 도넛은 고유 번호가 있고, 마드리드 경찰국은 범죄 정보와 그 범죄의 도넛 고유번호가 담긴 커다란 DB를 가지고 있다.

오늘은 너의 날이다. 너의 임무는 DB에 담긴 기록을 읽어 새로운 범죄 현장의 도넛과 유사한 도넛을 찾아내는 새로운 요원을 개발하는 것이다.

가상 범죄학 전문가들은 도넛 간의 유사성 판별의 기준을 제시했다. 그것은 도넛의 구멍의 반지름의 차와 도넛 전체의 반지름의 차의 합이다.

입력

모든 테스트 케이스는 첫 번째 줄에 DB 속의 도넛의 개수인 n이 주어진다. (1 ≤ n ≤ 100, 000)

그 뒤의 n개의 줄 중에서 i번째 줄은 i번째 도넛의 구멍의 반지름과 도넛 전체의 반지름을 나타내는 두 개의 정수 l과 w가 주어진다. (1 ≤ l, w ≤ 109)

그리고 나서는 당신이 DB에서 찾는 도넛의 개수를 나타내는 q가 주어진다. (1 ≤ q ≤ 50, 000)

그 뒤의 q개의 줄 중에서 i번째 줄은 i번째 도넛의 차원을 나타낸다.

다른 테스트 케이스는 빈 줄로 구분되며 입력의 종료 전에 -1이 주어진다.

출력

매 테스트 케이스의 출력물은 정수로 이루어진 q개의 줄이어야 한다. i번째 줄에는 새로 발견된 i번째 도넛과 가장 가까운 DB의 도넛 간의 유사도를 출력하라.

서로 다른 테스트 케이스에 대한 답안은 빈 줄로 구분되어야 한다.

예제 입력 1

2
2 3
3 4
2
1 1
3 4

2
1 1
9 9
4
4 5
6 5
2 5
3 4

-1

예제 출력 1

3
0

7
7
5
5
W3sicHJvYmxlbV9pZCI6IjM4MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM3NzRcdWJjODQgXHViM2M0XHViMTFiIFx1YmM5NFx1YzhjNCBcdWMyMThcdWMwYWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzExY1x1YWUzMCAyMDQyXHViMTQ0LiBcdWM3NzhcdWQxMzBcdWIxMzdcdWM3NDAgXHVhYzAwXHVjMGMxIFx1ZDYwNFx1YzJlNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjODE1XHViM2M0XHViODVjIFx1YmMxY1x1YzgwNFx1ZDU4OFx1YWNlMCBcdWMwYWNcdWM3NzRcdWJjODQgXHViYzk0XHVjOGM0XHViMjk0IFx1YjllNFx1Yzc3YyBcdWM3N2NcdWM1YjRcdWIwOWNcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyAyMDQxXHViMTQ0IFNXRVJDIFx1YjMwMFx1ZDY4YyBcdWM2YjBcdWMyYjlcdWM3OTBcdWIyOTQgXHVjMGFjXHVjNzc0XHViYzg0IFx1YmM5NFx1YzhjNFx1YWMwMCBcdWM3N2NcdWM1YjRcdWIwYTAgXHViNTRjXHViOWM4XHViMmU0IFx1YjNjNFx1YjExYlx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YWNcdWIyOTQgXHVjNjk0XHVjNmQwXHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU3NFx1YjBjOFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjNjNFx1YjExYlx1Yzc0MCBcdWFjZTBcdWM3MjAgXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHViOWM4XHViNGRjXHViOWFjXHViNGRjIFx1YWNiZFx1Y2MzMFx1YWQ2ZFx1Yzc0MCBcdWJjOTRcdWM4YzQgXHVjODE1XHViY2Y0XHVjNjQwIFx1YWRmOCBcdWJjOTRcdWM4YzRcdWM3NTggXHViM2M0XHViMTFiIFx1YWNlMFx1YzcyMFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWIyZjRcdWFlMzQgXHVjZWU0XHViMmU0XHViNzgwIERCXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YjI5OFx1Yzc0MCBcdWIxMDhcdWM3NTggXHViMGEwXHVjNzc0XHViMmU0LiBcdWIxMDhcdWM3NTggXHVjNzg0XHViYjM0XHViMjk0IERCXHVjNWQwIFx1YjJmNFx1YWUzNCBcdWFlMzBcdWI4NWRcdWM3NDQgXHVjNzdkXHVjNWI0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJjOTRcdWM4YzQgXHVkNjA0XHVjN2E1XHVjNzU4IFx1YjNjNFx1YjExYlx1YWNmYyBcdWM3MjBcdWMwYWNcdWQ1NWMgXHViM2M0XHViMTFiXHVjNzQ0IFx1Y2MzZVx1YzU0NFx1YjBiNFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNjk0XHVjNmQwXHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzBjMSBcdWJjOTRcdWM4YzRcdWQ1NTkgXHVjODA0XHViYjM4XHVhYzAwXHViNGU0XHVjNzQwIFx1YjNjNFx1YjExYiBcdWFjMDRcdWM3NTggXHVjNzIwXHVjMGFjXHVjMTMxIFx1ZDMxMFx1YmNjNFx1Yzc1OCBcdWFlMzBcdWM5MDBcdWM3NDQgXHVjODFjXHVjMmRjXHVkNTg4XHViMmU0LiBcdWFkZjhcdWFjODNcdWM3NDAgXHViM2M0XHViMTFiXHVjNzU4IFx1YWQ2Y1x1YmE0ZFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NTggXHVjYzI4XHVjNjQwIFx1YjNjNFx1YjExYiBcdWM4MDRcdWNjYjRcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzU4IFx1Y2MyOFx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBEQiBcdWMxOGRcdWM3NTggXHViM2M0XHViMTFiXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3OCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IG4gJmxlOyAxMDAsIDAwMCk8XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjRhNFx1Yzc1OCBuXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWM5MTFcdWM1ZDBcdWMxMWMgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgaVx1YmM4OFx1YzlmOCBcdWIzYzRcdWIxMWJcdWM3NTggXHVhZDZjXHViYTRkXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1YWNmYyBcdWIzYzRcdWIxMWIgXHVjODA0XHVjY2I0XHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggbFx1YWNmYyB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IGwsIHcgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwOThcdWMxMWNcdWIyOTQgXHViMmY5XHVjMmUwXHVjNzc0IERCXHVjNWQwXHVjMTFjIFx1Y2MzZVx1YjI5NCBcdWIzYzRcdWIxMWJcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBxXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IHEgJmxlOyA1MCwgMDAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViNGE0XHVjNzU4IHFcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMVx1YzVkMFx1YzExYyBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBpXHViYzg4XHVjOWY4IFx1YjNjNFx1YjExYlx1Yzc1OCBcdWNjMjhcdWM2ZDBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWI5NzggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YmE3MCBcdWM3ODVcdWI4MjVcdWM3NTggXHVjODg1XHViOGNjIFx1YzgwNFx1YzVkMCAtMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjZDljXHViODI1XHViYjNjXHVjNzQwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgcVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzhcdWI4NWMgXHViYzFjXHVhY2FjXHViNDFjIGlcdWJjODhcdWM5ZjggXHViM2M0XHViMTFiXHVhY2ZjIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgREJcdWM3NTggXHViM2M0XHViMTFiIFx1YWMwNFx1Yzc1OCBcdWM3MjBcdWMwYWNcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1YzU0OFx1Yzc0MCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzgzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkN5YmVyY3JpbWUgRG9udXQgSW52ZXN0aWdhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WWVhciAyMDQyLiBUaGUgSW50ZXJuZXQgaGFzIGV2b2x2ZWQgdG8gYSB2aXJ0dWFsIHJlYWxpdHkgZGF0YXNwYWNlIHdoZXJlIGNyaW1lcyBhcmUgY29tbWl0dGVkIGV2ZXJ5IGRheS4gVGhlIDIwNDEgU1dFUkMgd2lubmVyIGRldmVsb3BlZCBhbiBhZ2VudCB0aGF0IGRyb3BzIGEgZG9udXQgZXZlcnkgdGltZSBhIGNyaW1lIGlzIGNvbW1pdHRlZCBpbiB0aGUgQ3liZXJzcGFjZS4gRWFjaCBvZiB0aGUgZG9udXRzIGhhcyBpdHMgb3duIHNpZ25hdHVyZS4gVGhlIE1hZHJpZCBQb2xpY2UgaGF2ZSBhIGh1Z2UgZGF0YWJhc2Ugd2l0aCBjcmltZXMgYW5kIHRoZWlyIGRvbnV0IHNpZ25hdHVyZXMuPFwvcD5cclxuXHJcbjxwPlRvZGF5IGlzIHlvdXIgZGF5LiBZb3VyIHRhc2sgaXMgdG8gaW1wbGVtZW50IGEgbmV3IGFnZW50IHRoYXQgbG9va3MgZm9yIHRoZSByZWNvcmRzIGluIHRoZSBkYXRhYmFzZSB0aGF0IGJlYXIgYSBzdHJvbmcgcmVzZW1ibGFuY2UgdG8gdGhlIGdpdmVuIHNpZ25hdHVyZSBvZiBhIGRyb3BwZWQgZG9udXQgZm91bmQgYXQgYSBuZXcgY3JpbWUgc2NlbmUuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2NkaS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjJweDsgd2lkdGg6Mjg0cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIDI6IFRoZSBtYWpvciBwaWVjZSBvZiBldmlkZW5jZSBmb3IgdG9kYXkmcnNxdW87cyB1bnNvbHZlZCBjcmltZSBzdHJlYWs8XC9wPlxyXG5cclxuPHA+RXhwZXJ0cyBpbiB2aXJ0dWFsIGNyaW1pbm9sb2d5IGhhdmUgb2J0YWluZWQgdGhlIGJlc3Qgc2ltaWxhcml0eSBtZWFzdXJlIGJldHdlZW4gZG9udXRzOiBjb21wdXRlIHRoZSBkaWZmZXJlbmNlIGluIHJhZGl1cyBvZiB0aGUgaW50ZXJuYWwgcGFydCBvZiB0aGUgdG9yb2lkcyAoaG9sZXMpLCBjb21wdXRlIHRoZSBkaWZmZXJlbmNlIGluIHJhZGl1cyBvZiB0aGUgZXh0ZXJuYWwgcGFydCBvZiB0aGUgdG9yb2lkcyAodHViZXMpLCBhbmQgdGhlbiBhZGQgdXAgdGhvc2UgZGlmZmVyZW5jZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBuICgxICZsZTsgbiAmbGU7IDEwMCwgMDAwKSwgdGhlIG51bWJlciBvZiBkb251dHMgaW4gdGhlIGRhdGFiYXNlLiBUaGUgaXRoIG9mIHRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWlucyB0aGUgcmFkaXVzIG9mIHRoZSBob2xlIGFuZCByYWRpdXMgb2YgdGhlIHR1YmUgb2YgdGhlIGl0aCBkb251dCBpbiB0aGUgZGF0YWJhc2UsIGRlc2NyaWJlZCBieSB0d28gaW50ZWdlcnMgbCBhbmQgdyAoMSAmbGU7IGwsIHcgJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBBZnRlciB0aGF0IHRoZXJlIGlzIGEgbGluZSBjb250YWluaW5nIHEgKDEgJmxlOyBxICZsZTsgNTAsIDAwMCksIHRoZSBudW1iZXIgb2YgZG9udXRzIHRoYXQgeW91IGFyZSBsb29raW5nIGZvciBpbiB0aGUgZGF0YWJhc2UuIFRoZW4gcSBsaW5lcyBmb2xsb3csIHRoZSBpdGggb2YgdGhlbSBkZXNjcmliaW5nIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBuZXdseSBmb3VuZCBpdGggZG9udXQgaW4gdGhlIHNhbWUgd2F5LjxcL3A+XHJcblxyXG48cD5EaWZmZXJlbnQgdGVzdCBjYXNlcyBhcmUgc2VwYXJhdGVkIGJ5IGEgYmxhbmsgbGluZS4gQSBsaW5lIGNvbnRhaW5pbmcgJm1pbnVzOzEgbWFya3MgdGhlIGVuZCBvZiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBvZiB5b3VyIHByb2dyYW0gb24gZWFjaCB0ZXN0IGNhc2Ugc2hvdWxkIGhhdmUgcSBsaW5lcywgZWFjaCBvZiB0aGVtIGNvbnRhaW5pbmcgYW4gaW50ZWdlci4gVGhlIGl0aCBvZiB0aGVzZSBsaW5lcyBzaG91bGQgY29udGFpbiB0aGUgc2ltaWxhcml0eSBiZXR3ZWVuIHRoZSBuZXdseSBmb3VuZCBpdGggZG9udXQgYW5kIHRoZSBkb251dCBpbiB0aGUgZGF0YWJhc2UgdGhhdCBtb3N0IGNsb3NlbHkgcmVzZW1ibGVzIGl0LiBPdXRwdXRzIGZvciBkaWZmZXJlbnQgdGVzdCBjYXNlcyBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5IGEgYmxhbmsgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=