FPS

Minhyeok is spending his leave playing an FPS game. His team currently has N players. Each player has two stats: speed V and range R. Player A is better than player B if both A's speed and A's range are strictly greater than B's.

Minhyeok wants to add K bots to the game. Each bot also has speed and range. Among the selected bots, all speeds must be distinct and all ranges must be distinct. For example, after choosing a bot with stats (1, 2), no other selected bot may have speed 1 or range 2. A bot may have the same stat pair as a human player.

To keep the game from becoming too easy, every bot must have at least one human player who is better than that bot.

Before adding the bots, the team is waiting for one final player. There are Q candidates who want to join. For each candidate, compute the number of ways to choose K bots after adding that candidate to the team.

The first line contains N and K. (2 <= N <= 100,000, 1 <= K <= 30)

Each of the next N lines contains a player's speed and range Vi, Ri. (1 <= Vi, Ri <= 100,000)

The next line contains Q, the number of candidates. (1 <= Q <= 100,000)

Each of the next Q lines contains a candidate's speed and range Vi, Ri. (1 <= Vi, Ri <= 100,000)

Print Q lines. For each candidate, print the number of ways to choose K bots after adding that candidate, modulo 10009.

In the first visible test, the selectable bot stats are (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), and (3, 1).