P11781 [COTS 2012] 机器统计 / MULTI

有 $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$ 个新人时的方案数。

【样例解释】 关于样例 $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 \le 10^5,1 \le Q,a_i,b_i \le 10^5,1 \le K \le 30$。