题目描述

有 $n$ 个人，每个人有两个参数 $a_i,b_i$，我们称 $i$ 强于 $j$ 当且仅当 $a_i>a_j$ 且 $b_i>b_j$。

你需要添加 $K$ 个机器人，他们的参数由你自行决定，但要求不能有了两个机器人的参数完全相同，且对于每个机器人，要至少有一个人强于他。

现在有 $Q$ 个新人，对于每个新人，你需要计算当他和前面 $n$ 个人在一起时，添加机器人的方案数。方案数对 $10009$ 取模。

输入格式

一行两个整数 $n,K$，如题所示。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，表每个人参数。

接下来一行一个整数 $Q$，表示新人数量。

接下来 $Q$ 行，每行两个整数 $a_i,b_i$，表新人参数。

输出格式

$Q$ 行，第 $i$ 行表示加入第 $i$ 个新人时的方案数。

2 1 
2 5 
3 3 
1 
4 2

7

2 2 
5 2 
3 5 
2 
5 5 
1 3 

72
24

提示

【样例解释】

关于样例 $1$，合法的方案如下：$(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1)$。

【数据范围与约定】

对于 $44 \%$ 的数据，满足 $K=2$。

对于 $55 \%$ 的数据，满足 $Q=1$。

对于 $77 \%$ 的数据中，上述两者必有至少一者成立。

对于 $100 \%$ 的数据，满足 $2 \le n,Q,a_i,b_i \le 10^5,1 \le K \le 30$。