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

문제

민혁이가 휴학을 한 이유는 집에서 게임을 실컷 하기 위해서이다. 민혁이가 주로 하는 게임은 FPS 게임이다. 이 게임은 맵을 돌아다니면서 상대방을 물총으로 쏘는 게임이다. 지금 민혁이네 팀에는 총 N명의 플레이어가 게임을 하고 있다. 각 플레이어는 두 능력치 속도와 사정거리가 있다. 플레이어 A가 B보다 게임을 잘하려면 A의 두 능력치가 모두 B의 능력치보다 커야 한다.

민혁이는 게임을 더욱 재밌게 하기 위해서 봇 K개를 게임에 추가하려고 한다. 봇은 컴퓨터가 조정하며, 인간 플레이어와 동일한 방법으로 게임에 참가한다. 각 봇도 인간 플레이어와 같이 두 개의 능력치가 있다. 또, 봇의 능력치가 봇끼리 겹치는 경우는 없다. 즉, (1, 2)를 가진 봇을 선택한다면, 속도가 1이거나 사정거리가 2인 봇은 선택할 수 없다. (인간 플레이어와는 겹칠 수도 있다) 또, 봇이 너무 강력해서 게임이 재미 없어지는 것을 막기 위해서 각각의 봇보다 게임을 잘하는 인간 플레이어가 적어도 한 명은 있다. 

봇을 추가 하기 전에 민혁이네 팀은 지금 한 명을 기다리고 있다. 민혁이네 팀에 들어오고 싶어하는 플레이어는 총 Q명이다. 민혁이는 후보자 중 각각을 추가했을 때, 봇 K개를 선택하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ K ≤ 30)

다음 N개 줄에는 각 플레이어의 속도와 사정거리 Vi와 Ri가 주어진다. (1 ≤ Vi, Ri ≤ 100,000)

다음 줄에는 민혁이네 팀에 들어오려고 하는 사람의 수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q개 줄에는 민혁이네 팀에 들어오려고 하는 플레이어의 속도와 사정거리 Vi와 Ri가 주어진다. (1 ≤ Vi, Ri ≤ 100,000)

출력

총 Q개 줄에 각각의 후보가 민혁이네 참가했을 때, 봇 K개를 선택하는 방법의 수를 10009로 나눈 나머지를 출력한다.

예제 입력 1

2 1
2 5
3 3
1
4 2

예제 출력 1

7

힌트

능력치가 (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (3, 1)인 봇을 추가할 수 있다.

W3sicHJvYmxlbV9pZCI6IjMwODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJGUFMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ3MzRcdWQ1NTlcdWM3NDQgXHVkNTVjIFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJlNFx1Y2VmNyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHVjNzc0XHViMmU0LiBcdWJiZmNcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOGZjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDAgRlBTIFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI5ZjVcdWM3NDQgXHViM2NjXHVjNTQ0XHViMmU0XHViMmM4XHViYTc0XHVjMTFjIFx1YzBjMVx1YjMwMFx1YmMyOVx1Yzc0NCBcdWJiM2NcdWNkMWRcdWM3M2NcdWI4NWMgXHVjM2Q4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVjOWMwXHVhZTA4IFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjEyNCBcdWQzMDBcdWM1ZDBcdWIyOTQgXHVjZDFkIE5cdWJhODVcdWM3NTggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YjQ1MCBcdWIyYTVcdWI4MjVcdWNlNTggXHVjMThkXHViM2M0XHVjNjQwIFx1YzBhY1x1YzgxNVx1YWM3MFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNCBBXHVhYzAwIEJcdWJjZjRcdWIyZTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzc5OFx1ZDU1OFx1YjgyNFx1YmE3NCBBXHVjNzU4IFx1YjQ1MCBcdWIyYTVcdWI4MjVcdWNlNThcdWFjMDAgXHViYWE4XHViNDUwIEJcdWM3NTggXHViMmE1XHViODI1XHVjZTU4XHViY2Y0XHViMmU0IFx1Y2VlNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHViMzU0XHVjNmIxIFx1YzdhY1x1YmMwY1x1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmQwNyBLXHVhYzFjXHViOTdjIFx1YWM4Y1x1Yzc4NFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJkMDdcdWM3NDAgXHVjZWY0XHVkNGU4XHVkMTMwXHVhYzAwIFx1Yzg3MFx1YzgxNVx1ZDU1OFx1YmE3MCwgXHVjNzc4XHVhYzA0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YzY0MCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWJkMDdcdWIzYzQgXHVjNzc4XHVhYzA0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyYTVcdWI4MjVcdWNlNThcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YmQwN1x1Yzc1OCBcdWIyYTVcdWI4MjVcdWNlNThcdWFjMDAgXHViZDA3XHViMDdjXHViOWFjIFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM5ODksICgxLCAyKVx1Yjk3YyBcdWFjMDBcdWM5YzQgXHViZDA3XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjMThkXHViM2M0XHVhYzAwIDFcdWM3NzRcdWFjNzBcdWIwOTggXHVjMGFjXHVjODE1XHVhYzcwXHViOWFjXHVhYzAwIDJcdWM3NzggXHViZDA3XHVjNzQwIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiZuYnNwOyhcdWM3NzhcdWFjMDQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNjQwXHViMjk0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KSBcdWI2MTAsIFx1YmQwN1x1Yzc3NCBcdWIxMDhcdWJiMzQgXHVhYzE1XHViODI1XHVkNTc0XHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM3YWNcdWJiZjggXHVjNWM2XHVjNWI0XHVjOWMwXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJkMDdcdWJjZjRcdWIyZTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzc5OFx1ZDU1OFx1YjI5NCBcdWM3NzhcdWFjMDQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYTg1XHVjNzQwIFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViZDA3XHVjNzQ0IFx1Y2Q5NFx1YWMwMCBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjEyNCBcdWQzMDBcdWM3NDAgXHVjOWMwXHVhZTA4IFx1ZDU1YyBcdWJhODVcdWM3NDQgXHVhZTMwXHViMmU0XHViOWFjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMTI0IFx1ZDMwMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTU4XHViMjk0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWNkMWQgUVx1YmE4NVx1Yzc3NFx1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1ZDZjNFx1YmNmNFx1Yzc5MCBcdWM5MTEgXHVhYzAxXHVhYzAxXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YmQwNyBLXHVhYzFjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgSyAmbGU7IDMwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWMxOGRcdWIzYzRcdWM2NDAgXHVjMGFjXHVjODE1XHVhYzcwXHViOWFjIFZpXHVjNjQwIFJpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBWaSwgUmkgJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjEyNCBcdWQzMDBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjI0XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFEgJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYmZjXHVkNjAxXHVjNzc0XHViMTI0IFx1ZDMwMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWMxOGRcdWIzYzRcdWM2NDAgXHVjMGFjXHVjODE1XHVhYzcwXHViOWFjIFZpXHVjNjQwIFJpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBWaSwgUmkgJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZCBRXHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNmM0XHViY2Y0XHVhYzAwIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjEyNCBcdWNjMzhcdWFjMDBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWJkMDcgS1x1YWMxY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxMDAwOVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViMmE1XHViODI1XHVjZTU4XHVhYzAwJm5ic3A7KDEsIDEpLCAoMSwgMiksICgxLCAzKSwgKDEsIDQpLCAoMiwgMSksICgyLCAyKSwgKDMsIDEpXHVjNzc4IFx1YmQwN1x1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNVUxUSSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIGluZmFtb3VzIG9ubGluZSBtdWx0aXBsYXllciB2aWRlbyBnYW1lIGlzIGN1cnJlbnRseSBiZWluZyBwbGF5ZWQgYnkgTiBwZW9wbGUuIFRoZSBnb2FsIG9mIHRoZSBnYW1lIGlzIHRvIG1vdmUgYXJvdW5kIHRoZSBtYXAgYW5kIHNob290IG90aGVyIHBsYXllcnMgd2l0aCB3YXRlciBndW5zIG9mIGFsbCBzb3J0cy4gRXZlcnkgcGxheWVyIGNhbiBtb3ZlIHdpdGggY2VydGFpbiBzcGVlZCBhbmQgaGFzIGEgc2luZ2xlIGd1biBvZiBkZXRlcm1pbmVkIHJhbmdlLiBXZSBjYW4gc2F5IHRoYXQgcGxheWVyIEEgaXMgbXVjaCBiZXR0ZXIgdGhhbiBwbGF5ZXIgQiBpZiBib3RoIG9mIHRoZXNlIHBhcmFtZXRlcnMgKHNwZWVkIGFuZCBndW4gcmFuZ2UpIGFyZSBzdHJpY3RseSBncmVhdGVyIGZvciBwbGF5ZXIgQSB0aGFuIGZvciBwbGF5ZXIgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gbWFrZSB0aGUgZ2FtZSBtb3JlIGludGVyZXN0aW5nLCB0aGUgcHJvZ3JhbW1lcnMgd2lsbCBhZGQgSyBib3RzIGludG8gdGhlIGdhbWUuIEJvdHMgYXJlIGNvbnRyb2xsZWQgYnkgYSBjb21wdXRlciBhbmQgcGFydGljaXBhdGUgaW4gdGhlIGdhbWUgaW4gdGhlIHNhbWUgbWFubmVyIGFzIG5vcm1hbCBwbGF5ZXJzLiBFYWNoIGJvdCBpcyBkZXRlcm1pbmVkIGJ5IHNhbWUgdHdvIHBhcmFtZXRlcnMgYXMgbm9ybWFsIHBsYXllcnMsIGJ1dCB0byBtYWtlIHRoZW0gZGlzdGluZ3Vpc2hhYmxlLCB0aGV5IGFsbCBtdXN0IGhhdmUgZGlzdGluY3Qgc3BlZWRzIGFuZCBkaXN0aW5jdCBndW4gcmFuZ2VzICh0aGlzIGRvZXNuJiMzOTt0IGluY2x1ZGUgcGxheWVycykuIEluIG9yZGVyIGZvciBib3RzIG5vdCB0byBiZSBvdmVycG93ZXJlZCwgZm9yIGVhY2ggYm90IHRoZXJlIG11c3QgYmUgYSBub3JtYWwgcGxheWVyIHRoYXQgaXMgbXVjaCBiZXR0ZXIgdGhhbiB0aGF0IGJvdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QmVmb3JlIHRoZSBib3RzIGFyZSBhZGRlZCwgdGhlIHBsYXllcnMgYXJlIHdhaXRpbmcgZm9yIG9uZSBtb3JlIG5vcm1hbCBwbGF5ZXIgdG8gam9pbiB0aGUgZ2FtZS4gWW91ciB0YXNrIGlzIHRoYXQgZm9yIGVhY2ggb2YgUSBjYW5kaWRhdGUgbmV3IHBsYXllcnMgZGV0ZXJtaW5lIHRoZSBmb2xsb3dpbmc6IGlmIHRoYXQgcGxheWVyIGpvaW5zIHRoZSBOIGV4aXN0aW5nIHBsYXllcnMsIG9uIGhvdyBtYW55IGRpc3RpbmN0IHdheXMgY2FuIHlvdSBzZWxlY3QgYW5kIGFkZCBLIGJvdHMgdG8gdGhlIGdhbWU/IFR3byBib3Qgc2VsZWN0aW9ucyBhcmUgY29uc2lkZXJlZCBkaWZmZXJlbnQgaWYgdGhlcmUgaXMgYSBzaW5nbGUgYm90IGluIG9uZSBzZWxlY3Rpb24gdGhhdCBkb2VzbiYjMzk7dCBleGlzdCBpbiB0aGUgb3RoZXIgc2VsZWN0aW9uLiBUaGlzIG51bWJlciBjYW4gYmUgcXVpdGUgaHVnZSwgc28gd3JpdGUgaXQgbW9kdWxvIDEwIDAwOS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBOICZsZTsgMTAwIDAwMCwgMSAmbGU7IEsgJmxlOyAzMCksIHRoZSBudW1iZXIgb2YgcGxheWVycyBhbmQgdGhlIG51bWJlciBvZiBib3RzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiBwYXJhbWV0ZXJzIGZvciB0aGUgcGxheWVycywgVjxzdWI+aTxcL3N1Yj4gYW5kIFI8c3ViPmk8XC9zdWI+ICgxICZsZTsgVjxzdWI+aTxcL3N1Yj4sIFI8c3ViPmk8XC9zdWI+ICZsZTsgMTAwIDAwMCksIHNwZWVkIGFuZCBndW4gcmFuZ2UgZm9yIHBsYXllciBpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5OZXh0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgUSAoMSAmbGU7IFEgJmxlOyAxMDAgMDAwKSwgbnVtYmVyIG9mIGNhbmRpZGF0ZSBwbGF5ZXJzIHRoYXQgY291bGQgam9pbiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGFzdCBRIGxpbmVzIGNvbnRhaW4gZ2FtZSBwYXJhbWV0ZXJzIGZvciB0aGUgY2FuZGlkYXRlIHBsYXllcnMsIFY8c3ViPmk8XC9zdWI+IGFuZCBSPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IFY8c3ViPmk8XC9zdWI+LCBSPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCAwMDApLCBzcGVlZCBhbmQgZ3VuIHJhbmdlIGZvciBjYW5kaWRhdGUgcGxheWVyIGkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91IG5lZWQgdG8gb3V0cHV0IGEgdG90YWwgb2YgUSBsaW5lcywgb25lIGZvciBlYWNoIGNhbmRpZGF0ZSBwbGF5ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIGNhbmRpZGF0ZSBwbGF5ZXIgSiBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHdheXMgKG1vZHVsbyAxMDAwOSkgdG8gc2VsZWN0IEsgYm90cyBpZiB0aGF0IGNhbmRpZGF0ZSBwbGF5ZXIgd291bGQgam9pbiB0aGUgb3RoZXIgTiBwbGF5ZXJzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==