컬러 그림 판매

루카는 그림을 파는 상인이다. 고객은 $N$명이고, 루카는 고객 한 명 한 명에게 그림을 판다.

모든 고객은 컬러 그림만 사거나 흑백 그림만 산다. 한 고객이 두 종류를 함께 사지는 않는다. $i$번 고객은 컬러 그림을 최대 $a_i$장, 흑백 그림을 최대 $b_i$장 사며, 어느 쪽을 고르든 최소 한 장은 산다. 루카의 재고는 충분히 많아서 고객이 원하는 수량을 채우지 못하는 일은 없다.

루카는 흑백 그림을 파는 것을 싫어한다. 컬러 그림을 받는 고객이 $C$명보다 적으면 루카는 기분이 상한다.

고객은 자기가 사려는 최대 장수를 자주 바꾼다. 장수가 바뀔 때마다, 컬러 그림을 한 장 이상 받는 고객이 $C$명 이상인 판매 방법의 수를 구하라.

첫째 줄에 정수 $N$과 $C$가 주어진다 ($1 \le N \le 100000$, $1 \le C \le 20$).

둘째 줄에 $N$개의 정수 $a_i$가 주어진다 ($1 \le a_i \le 10^9$).

셋째 줄에 $N$개의 정수 $b_i$가 주어진다 ($1 \le b_i \le 10^9$).

넷째 줄에 변경 횟수 $Q$가 주어진다 ($1 \le Q \le 100000$).

다음 $Q$개 줄에 정수 $P$, $a_P$, $b_P$가 주어진다 ($1 \le P \le N$, $1 \le a_P \le 10^9$, $1 \le b_P \le 10^9$). $P$번 고객이 사려는 컬러 그림의 최대 장수를 $a_P$로, 흑백 그림의 최대 장수를 $b_P$로 바꾼다는 뜻이다. 각 변경은 그대로 남아 이후 질의에도 적용된다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 변경 직후의 판매 방법의 수를 $10007$로 나눈 나머지를 출력한다.

고객 한 명이라도 사는 그림의 종류가 다르거나 장수가 다르면 서로 다른 판매 방법이다. 그래서 고객 한 명은 컬러 그림을 살 때 $a_i$가지, 흑백 그림을 살 때 $b_i$가지 경우를 만든다. $C$가 $N$보다 크면 조건을 만족하는 방법이 없으므로 답은 0이다.