시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 32 3 2 9.524%

문제

민혁이가 휴학을 한 이유는 집에서 게임을 실컷 하기 위해서이다. 민혁이가 주로 하는 게임은 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로 나눈 나머지를 출력한다.

예제 입력

2 1
2 5
3 3
1
4 2

예제 출력

7

힌트

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