시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 306 100 64 38.323%

문제

정부는 오크 나무 숲을 통과하는 산책길를 만들려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 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+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGtmb3Jlc3QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjM1cHg7IHdpZHRoOjI1MnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIUkFTVE9WSSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGdvdmVybm1lbnQgaXMgcGxhbmluZyB0byBidWlsZCBhIHdhbGt3YXkgZm9yIHRvdXJpc3RzIGluIHRoZSBtaWRkbGUgb2YgYW4gb2FrIGZvcmVzdC4gVGhlIGZvcmVzdCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgcGxhbmUgd2l0aCBOIHNwZWNpYWwgbGF0dGljZSBwb2ludHMgcmVwcmVzZW50aW5nIG9ha3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB3YWxrd2F5IGlzIHJlcHJlc2VudGVkIGFzIGEgcmVjdGFuZ2xlIHdpdGggc2lkZXMgcGFyYWxsZWwgdG8gdGhlIGF4ZXMuIElmIHRoZSBzaWRlcyBvZiB3YWxrd2F5IHJlY3RhbmdsZSBpbnRlcnNlY3QgYW55IG9hayBsYXR0aWNlIHBvaW50cywgc3VjaCBvYWtzIG5lZWQgdG8gYmUgYXhlZCBkb3duLiBPYWtzIGluc2lkZSB0aGUgcmVjdGFuZ2xlIGRvIG5vdCByZXByZXNlbnQgcHJvYmxlbXMgYW5kIG5lZWQgbm90IGJlIGN1dCBkb3duLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ManVibyBpcyB0aGUgc3RhdGUgc2VjcmV0YXJ5IG9mIEZvcmVzdHJ5IGFuZCBhbiBwYXNzaW9uYXRlIG5hdHVyZSBsb3Zlciwgc28gaGUgb3JkZXJlZCB0aGUgc2VjcmV0YXJ5IG9mIFRvdXJpc20gdG8gcHJvdmlkZSBoaW0gd2l0aCBhIGxpc3Qgb2YgUCBwb3NzaWJsZSByZWN0YW5nbGUgd2Fsa3dheXMgdGhhdCBhcmUgYXR0cmFjdGl2ZSBlbm91Z2ggdG8gZHJhdyBpbiB0b3VyaXN0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGp1Ym8gcGxhbnMgdG8gc2VsZWN0IHRoZSB3YWxrd2F5IHRoYXQgbmVlZHMgdGhlIHNtYWxsZXN0IGFtb3VudCBvZiBvYWsgdHJlZXMgdG8gYmUgY3V0IGRvd24uIFNpbmNlIHdlIGFsc28gbGlrZSB0cmVlcywgd291bGQgeW91IGJlIHNvIGtpbmQgYW5kIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2Ygb2FrcyB0aGF0IHdpbGwgYmUgY3V0IGRvd24gZm9yIGVhY2ggd2Fsa3dheS4gUmVtZW1iZXIgb25seSB0aGUgb2FrcyBpbnRlcnNlY3RpbmcgdGhlIHNpZGVzIG9mIHRoZSByZWN0YW5nbGUgbmVlZCB0byBiZSBjdXQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCBudW1iZXIgb2Ygb2Frcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2VycyBlYWNoIFggaSBZICgxICZsZTsgWCwgWSAmbGU7IDEwPHN1cD45PFwvc3VwPikgY29vcmRpbmF0ZXMgb2Ygb2Frcy4gVGhlcmUgd2lsbCBiZSBhdCBtb3N0IG9uZSBvYWsgb24gZWFjaCBsYXR0aWNlIHBvaW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIFAgKDEgJmxlOyBQICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiB3YWxrd2F5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgUCBsaW5lcyBjb250YWluIGZvdXIgaW50ZWdlcnMgZWFjaCBYMSwgWTEsIFgyIGkgWTIgKDEgJmxlOyBYMSAmbHQ7IFgyICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAxICZsZTsgWTEgJmx0OyBZMiAmbGU7IDEwPHN1cD45PFwvc3VwPikgY29vcmRpbmF0ZXMgb2YgdGhlIGxvd2VyIGxlZnQgKFgxLCBZMSkgYW5kIHVwcGVyIHJpZ2h0IChYMiwgWTIpIGNvcm5lciBvZiB0aGUgcmVjdGFuZ2xlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBQIGludGVnZXJzLCBvbmUgcGVyIGxpbmUsIHRoZSBudW1iZXIgb2Ygb2FrcyB0aGF0IG5lZWQgdG8gYmUgY3V0IGRvd24gZm9yIGVhY2ggd2Fsa3dheSBpbiB0aGUgb3JkZXIgdGhleSBhcmUgcHJlc2VudGVkIGluIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==