시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1YzU0OFx1Yzc0MCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ3liZXJjcmltZSBEb251dCBJbnZlc3RpZ2F0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5ZZWFyIDIwNDIuIFRoZSBJbnRlcm5ldCBoYXMgZXZvbHZlZCB0byBhIHZpcnR1YWwgcmVhbGl0eSBkYXRhc3BhY2Ugd2hlcmUgY3JpbWVzIGFyZSBjb21taXR0ZWQgZXZlcnkgZGF5LiBUaGUgMjA0MSBTV0VSQyB3aW5uZXIgZGV2ZWxvcGVkIGFuIGFnZW50IHRoYXQgZHJvcHMgYSBkb251dCBldmVyeSB0aW1lIGEgY3JpbWUgaXMgY29tbWl0dGVkIGluIHRoZSBDeWJlcnNwYWNlLiBFYWNoIG9mIHRoZSBkb251dHMgaGFzIGl0cyBvd24gc2lnbmF0dXJlLiBUaGUgTWFkcmlkIFBvbGljZSBoYXZlIGEgaHVnZSBkYXRhYmFzZSB3aXRoIGNyaW1lcyBhbmQgdGhlaXIgZG9udXQgc2lnbmF0dXJlcy48XC9wPlxyXG5cclxuPHA+VG9kYXkgaXMgeW91ciBkYXkuIFlvdXIgdGFzayBpcyB0byBpbXBsZW1lbnQgYSBuZXcgYWdlbnQgdGhhdCBsb29rcyBmb3IgdGhlIHJlY29yZHMgaW4gdGhlIGRhdGFiYXNlIHRoYXQgYmVhciBhIHN0cm9uZyByZXNlbWJsYW5jZSB0byB0aGUgZ2l2ZW4gc2lnbmF0dXJlIG9mIGEgZHJvcHBlZCBkb251dCBmb3VuZCBhdCBhIG5ldyBjcmltZSBzY2VuZS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvY2RpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2MnB4OyB3aWR0aDoyODRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMjogVGhlIG1ham9yIHBpZWNlIG9mIGV2aWRlbmNlIGZvciB0b2RheSZyc3F1bztzIHVuc29sdmVkIGNyaW1lIHN0cmVhazxcL3A+XHJcblxyXG48cD5FeHBlcnRzIGluIHZpcnR1YWwgY3JpbWlub2xvZ3kgaGF2ZSBvYnRhaW5lZCB0aGUgYmVzdCBzaW1pbGFyaXR5IG1lYXN1cmUgYmV0d2VlbiBkb251dHM6IGNvbXB1dGUgdGhlIGRpZmZlcmVuY2UgaW4gcmFkaXVzIG9mIHRoZSBpbnRlcm5hbCBwYXJ0IG9mIHRoZSB0b3JvaWRzIChob2xlcyksIGNvbXB1dGUgdGhlIGRpZmZlcmVuY2UgaW4gcmFkaXVzIG9mIHRoZSBleHRlcm5hbCBwYXJ0IG9mIHRoZSB0b3JvaWRzICh0dWJlcyksIGFuZCB0aGVuIGFkZCB1cCB0aG9zZSBkaWZmZXJlbmNlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIG4gKDEgJmxlOyBuICZsZTsgMTAwLCAwMDApLCB0aGUgbnVtYmVyIG9mIGRvbnV0cyBpbiB0aGUgZGF0YWJhc2UuIFRoZSBpdGggb2YgdGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW5zIHRoZSByYWRpdXMgb2YgdGhlIGhvbGUgYW5kIHJhZGl1cyBvZiB0aGUgdHViZSBvZiB0aGUgaXRoIGRvbnV0IGluIHRoZSBkYXRhYmFzZSwgZGVzY3JpYmVkIGJ5IHR3byBpbnRlZ2VycyBsIGFuZCB3ICgxICZsZTsgbCwgdyAmbGU7IDEwPHN1cD45PFwvc3VwPikuIEFmdGVyIHRoYXQgdGhlcmUgaXMgYSBsaW5lIGNvbnRhaW5pbmcgcSAoMSAmbGU7IHEgJmxlOyA1MCwgMDAwKSwgdGhlIG51bWJlciBvZiBkb251dHMgdGhhdCB5b3UgYXJlIGxvb2tpbmcgZm9yIGluIHRoZSBkYXRhYmFzZS4gVGhlbiBxIGxpbmVzIGZvbGxvdywgdGhlIGl0aCBvZiB0aGVtIGRlc2NyaWJpbmcgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIG5ld2x5IGZvdW5kIGl0aCBkb251dCBpbiB0aGUgc2FtZSB3YXkuPFwvcD5cclxuXHJcbjxwPkRpZmZlcmVudCB0ZXN0IGNhc2VzIGFyZSBzZXBhcmF0ZWQgYnkgYSBibGFuayBsaW5lLiBBIGxpbmUgY29udGFpbmluZyAmbWludXM7MSBtYXJrcyB0aGUgZW5kIG9mIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IG9mIHlvdXIgcHJvZ3JhbSBvbiBlYWNoIHRlc3QgY2FzZSBzaG91bGQgaGF2ZSBxIGxpbmVzLCBlYWNoIG9mIHRoZW0gY29udGFpbmluZyBhbiBpbnRlZ2VyLiBUaGUgaXRoIG9mIHRoZXNlIGxpbmVzIHNob3VsZCBjb250YWluIHRoZSBzaW1pbGFyaXR5IGJldHdlZW4gdGhlIG5ld2x5IGZvdW5kIGl0aCBkb251dCBhbmQgdGhlIGRvbnV0IGluIHRoZSBkYXRhYmFzZSB0aGF0IG1vc3QgY2xvc2VseSByZXNlbWJsZXMgaXQuIE91dHB1dHMgZm9yIGRpZmZlcmVudCB0ZXN0IGNhc2VzIHNob3VsZCBiZSBzZXBhcmF0ZWQgYnkgYSBibGFuayBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d