MULTI

문제

One infamous online multiplayer video game is currently being played by N people. The goal of the game is to move around the map and shoot other players with water guns of all sorts. Every player can move with certain speed and has a single gun of determined range. We can say that player A is much better than player B if both of these parameters (speed and gun range) are strictly greater for player A than for player B. 

To make the game more interesting, the programmers will add K bots into the game. Bots are controlled by a computer and participate in the game in the same manner as normal players. Each bot is determined by same two parameters as normal players, but to make them distinguishable, they all must have distinct speeds and distinct gun ranges (this doesn't include players). In order for bots not to be overpowered, for each bot there must be a normal player that is much better than that bot. 

Before the bots are added, the players are waiting for one more normal player to join the game. Your task is that for each of Q candidate new players determine the following: if that player joins the N existing players, on how many distinct ways can you select and add K bots to the game? Two bot selections are considered different if there is a single bot in one selection that doesn't exist in the other selection. This number can be quite huge, so write it modulo 10 009.

입력

First line contains two integers N and K (2 ≤ N ≤ 100 000, 1 ≤ K ≤ 30), the number of players and the number of bots. 

The following N lines contain parameters for the players, V_i and R_i (1 ≤ V_i, R_i ≤ 100 000), speed and gun range for player i. 

Next line contains one integer Q (1 ≤ Q ≤ 100 000), number of candidate players that could join the game. 

Last Q lines contain game parameters for the candidate players, V_i and R_i (1 ≤ V_i, R_i ≤ 100 000), speed and gun range for candidate player i. 

출력

You need to output a total of Q lines, one for each candidate player. 

For each candidate player J output one line containing the number of ways (modulo 10009) to select K bots if that candidate player would join the other N players. 

힌트

Explanation of sample #1: Speed and gun range of the bot can be any of the following: (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) and (3, 1).

2 1
2 5
3 3
1
4 2

7

2 2
5 2
3 5
2
5 5
1 3

72
24