FPS

민혁이는 휴학 기간 동안 FPS 게임을 즐기고 있다. 그의 팀에는 현재 N명의 플레이어가 있으며, 각 플레이어는 속도 V와 사정거리 R 두 능력치를 가진다. 플레이어 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, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (3, 1)인 봇을 선택할 수 있다.