시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB4171389341.704%

문제

정부는 오크 나무 숲을 통과하는 산책길를 만들려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 N개는 평면위의 격자점으로 나타낼 수 있다.

산책길은 축에 평행한 직사각형으로 나타낸다. 산책길의 변 위에 있는 나무는 베어내야 한다. 산책길 내부에 있는 나무는 문제가 되지 않으며, 베어내지 않아도 된다.

산림청에서는 산책길 계획을 공모전으로 열었고, 총 P개의 산책길가 접수되었다. 각각의 접수된 산책길에 대해서, 그 산책길를 만들려면 나무를 몇 개나 잘라내야하는지 구하는 프로그램을 작성하시오. 나무는 변 위에 있는 나무만 베어야한다.

입력

첫째 줄에 나무의 수 N이 주어진다. (1 ≤ N ≤ 300,000)

다음 N개 줄에는 나무의 좌표 X와 Y가 한 줄에 하나씩 주어진다. 한 점위에 나무가 두 개 이상 있는 경우는 없다. (1 ≤ X, Y ≤ 109)

다음 줄에는 접수된 산책로 계획의 수 P (1 ≤ P ≤ 100,000)가 주어진다.

다음 P개 줄에는 X1, Y1, X2, Y2 (1 ≤ X1 < X2 ≤ 109, 1 ≤ Y1 < Y2 ≤ 109)가 주어진다. (X1, Y1)은 직사각형의 왼쪽 아래 좌표, (X2, Y2)는 오른쪽 위 좌표를 나타낸다.

출력

총 P개의 줄에 각 산책로를 건설하려면 나무를 몇 개나 베어야 하는지 출력한다. 입력으로 주어진 순서를 지켜 출력한다.

예제 입력 1

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

예제 출력 1

3
4
0
1

힌트

W3sicHJvYmxlbV9pZCI6IjI4ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYjBcdWNjNDVcdWFlMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YmQ4MFx1YjI5NCBcdWM2MjRcdWQwNmMgXHViMDk4XHViYjM0IFx1YzIzMlx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTQgXHVjMGIwXHVjYzQ1XHVhZTM4XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIzMlx1Yzc0NCBcdWQzYzlcdWJhNzRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmIzNCBOXHVhYzFjXHViMjk0IFx1ZDNjOVx1YmE3NFx1YzcwNFx1Yzc1OCBcdWFjYTlcdWM3OTBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBiMFx1Y2M0NVx1YWUzOFx1Yzc0MCBcdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTVjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzBiMFx1Y2M0NVx1YWUzOFx1Yzc1OCBcdWJjYzAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWIyOTQgXHViY2EwXHVjNWI0XHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMGIwXHVjYzQ1XHVhZTM4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHViMjk0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWJjYTBcdWM1YjRcdWIwYjRcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGIwXHViOWJjXHVjY2FkXHVjNWQwXHVjMTFjXHViMjk0IFx1YzBiMFx1Y2M0NVx1YWUzOCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVhY2Y1XHViYWE4XHVjODA0XHVjNzNjXHViODVjIFx1YzVmNFx1YzVjOFx1YWNlMCwgXHVjZDFkIFBcdWFjMWNcdWM3NTggXHVjMGIwXHVjYzQ1XHVhZTM4XHVhYzAwIFx1YzgxMVx1YzIxOFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzgxMVx1YzIxOFx1YjQxYyBcdWMwYjBcdWNjNDVcdWFlMzhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkZjggXHVjMGIwXHVjYzQ1XHVhZTM4XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YmE3NCBcdWIwOThcdWJiMzRcdWI5N2MgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWM3OThcdWI3N2NcdWIwYjRcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjA5OFx1YmIzNFx1YjI5NCBcdWJjYzAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5Y2MgXHViY2EwXHVjNWI0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIwOThcdWJiMzRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBYXHVjNjQwIFlcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NWMgXHVjODEwXHVjNzA0XHVjNWQwIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gKDEgJmxlOyBYLCBZICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMVx1YzIxOFx1YjQxYyBcdWMwYjBcdWNjNDVcdWI4NWMgXHVhY2M0XHVkNjhkXHVjNzU4IFx1YzIxOCBQICgxICZsZTsgUCAmbGU7IDEwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFBcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFgxLCBZMSwgWDIsIFkyICgxICZsZTsgWDEgJmx0OyBYMiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IFkxICZsdDsgWTIgJmxlOyAxMDxzdXA+OTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFgxLCBZMSlcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OTggXHVjODhjXHVkNDVjLCAoWDIsIFkyKVx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzA0IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkIFBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWMwYjBcdWNjNDVcdWI4NWNcdWI5N2MgXHVhYzc0XHVjMTI0XHVkNTU4XHViODI0XHViYTc0IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWJhODcgXHVhYzFjXHViMDk4IFx1YmNhMFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM5YzBcdWNmMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2YxNzgwYTI5LWQ5YTEtNDU2OC1hNDU4LWMyZWM1MWZiMjE4MVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjE3cHg7IGhlaWdodDogMjE4cHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSFJBU1RPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBnb3Zlcm5tZW50IGlzIHBsYW5pbmcgdG8gYnVpbGQgYSB3YWxrd2F5IGZvciB0b3VyaXN0cyBpbiB0aGUgbWlkZGxlIG9mIGFuIG9hayBmb3Jlc3QuIFRoZSBmb3Jlc3QgY2FuIGJlIHJlcHJlc2VudGVkIGFzIHBsYW5lIHdpdGggTiBzcGVjaWFsIGxhdHRpY2UgcG9pbnRzIHJlcHJlc2VudGluZyBvYWtzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgd2Fsa3dheSBpcyByZXByZXNlbnRlZCBhcyBhIHJlY3RhbmdsZSB3aXRoIHNpZGVzIHBhcmFsbGVsIHRvIHRoZSBheGVzLiBJZiB0aGUgc2lkZXMgb2Ygd2Fsa3dheSByZWN0YW5nbGUgaW50ZXJzZWN0IGFueSBvYWsgbGF0dGljZSBwb2ludHMsIHN1Y2ggb2FrcyBuZWVkIHRvIGJlIGF4ZWQgZG93bi4gT2FrcyBpbnNpZGUgdGhlIHJlY3RhbmdsZSBkbyBub3QgcmVwcmVzZW50IHByb2JsZW1zIGFuZCBuZWVkIG5vdCBiZSBjdXQgZG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGp1Ym8gaXMgdGhlIHN0YXRlIHNlY3JldGFyeSBvZiBGb3Jlc3RyeSBhbmQgYW4gcGFzc2lvbmF0ZSBuYXR1cmUgbG92ZXIsIHNvIGhlIG9yZGVyZWQgdGhlIHNlY3JldGFyeSBvZiBUb3VyaXNtIHRvIHByb3ZpZGUgaGltIHdpdGggYSBsaXN0IG9mIFAgcG9zc2libGUgcmVjdGFuZ2xlIHdhbGt3YXlzIHRoYXQgYXJlIGF0dHJhY3RpdmUgZW5vdWdoIHRvIGRyYXcgaW4gdG91cmlzdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxqdWJvIHBsYW5zIHRvIHNlbGVjdCB0aGUgd2Fsa3dheSB0aGF0IG5lZWRzIHRoZSBzbWFsbGVzdCBhbW91bnQgb2Ygb2FrIHRyZWVzIHRvIGJlIGN1dCBkb3duLiBTaW5jZSB3ZSBhbHNvIGxpa2UgdHJlZXMsIHdvdWxkIHlvdSBiZSBzbyBraW5kIGFuZCB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIG9ha3MgdGhhdCB3aWxsIGJlIGN1dCBkb3duIGZvciBlYWNoIHdhbGt3YXkuIFJlbWVtYmVyIG9ubHkgdGhlIG9ha3MgaW50ZXJzZWN0aW5nIHRoZSBzaWRlcyBvZiB0aGUgcmVjdGFuZ2xlIG5lZWQgdG8gYmUgY3V0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgbnVtYmVyIG9mIG9ha3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgZWFjaCBYIGFuZCBZICgxICZsZTsgWCwgWSAmbGU7IDEwPHN1cD45PFwvc3VwPikgY29vcmRpbmF0ZXMgb2Ygb2Frcy4gVGhlcmUgd2lsbCBiZSBhdCBtb3N0IG9uZSBvYWsgb24gZWFjaCBsYXR0aWNlIHBvaW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIFAgKDEgJmxlOyBQICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiB3YWxrd2F5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgUCBsaW5lcyBjb250YWluIGZvdXIgaW50ZWdlcnMgZWFjaCBYMSwgWTEsIFgyIGFuZCBZMiAoMSAmbGU7IFgxICZsdDsgWDIgJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDEgJmxlOyBZMSAmbHQ7IFkyICZsZTsgMTA8c3VwPjk8XC9zdXA+KSBjb29yZGluYXRlcyBvZiB0aGUgbG93ZXIgbGVmdCAoWDEsIFkxKSBhbmQgdXBwZXIgcmlnaHQgKFgyLCBZMikgY29ybmVyIG9mIHRoZSByZWN0YW5nbGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IFAgaW50ZWdlcnMsIG9uZSBwZXIgbGluZSwgdGhlIG51bWJlciBvZiBvYWtzIHRoYXQgbmVlZCB0byBiZSBjdXQgZG93biBmb3IgZWFjaCB3YWxrd2F5IGluIHRoZSBvcmRlciB0aGV5IGFyZSBwcmVzZW50ZWQgaW4gdGhlIGlucHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Croatian Olympiad in Informatics 2010 1번