시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
4.0 초 32 MB 1 1 (100%) 1
문제
시간 제한 4초, 메모리 제한 32MB 소년 Luka는 미술품 딜러이다. 그에게는 $N$명의 고객들이 있고 이들 각각에게 미술품들을 판매한다. 각 고객들은 유색의 혹은 흑백의 그림을 살 수 있는데 동시에 구매하지는 못한다. $i$번 고객은 최대 $a_i$개의 유색 그림을 구매하고자 하고 최대 $b_i$개의 흑백 그림을 구매하고자 한다. 고객들은 항상 적어도 한 개 이상의 그림을 구매할 것이다. Luka는 거의 셀수없이 많은 그림을 가지고 있기 때문에 그가 가지고 있는 총 그림의 수는 고려하지 않아도 된다. Luka는 흑백 그림을 판매하기 싫어하고 $C$명보다 적은 수의 고객이 유색 그림을 구매하게 된다면 실망하게 될 것이다. 그의 고객들은 지속적으로 요구사항을 바꾸는데 즉 그들이 구매하고자 하는 그림의 개수를 바꾸게 된다. 이것 때문에 Luka는 다음과 같은 문제를 해결하는데 종종 어려움을 겪는다: "적어도 $C$명의 고객이 유색 그림을 구매하게 하는 판매 방법의 가지수는?" Luka를 도와서 그가 안심할 수 있도록 지켜주자.
입력
첫째 줄에 두 개의 정수 $N, C(1 ≤ N ≤ 100,000, 1 ≤ C ≤ 20)$가 주어진다. 둘째 줄에는 $N$개의 정수 $a_i(1 ≤ a_i ≤ 1,000,000,000)$가 주어진다. 셋째 줄에는 $N$개의 정수 $b_i(1 ≤ b_i ≤ 1,000,000,000)$가 주어진다. 넷째 줄에는 요구사항이 변하는 횟수 $Q(1 ≤ Q ≤ 100,000)$가 주어진다. 다음 $Q$개의 줄에는 각각 3개의 정수가 있는데 변경을 요구하는 고객의 번호 $P(1 ≤ P ≤ N)$, 그가 원하는 유색 그림의 최대 개수 $a_p(1 ≤ a_p ≤ 1,000,000,000)$, 그가 원하는 흑백 그림의 최대 개수 $b_p(1 ≤ b_p ≤ 1,000,000,000)$이다.
출력
출력은 $Q$개의 줄을 따라서 가능한 판매 방법의 가지수를 $10,007$로 나눈 나머지를 출력한다.
힌트
#### 점수 30%의 경우에 $N, Q$는 $1000$보다 작을 것이다. #### 예제 입력 1 ``` 2 2 1 1 1 1 1 1 1 1 ``` #### 예제 출력 1 ``` 1 ``` #### 예제 입력 2 ``` 2 2 1 2 2 3 2 1 2 2 2 2 2 ``` #### 예제 출력 2 ``` 4 4 ``` #### 예제 입력 3 ``` 4 2 1 2 3 4 1 2 3 4 1 4 1 1 ``` #### 예제 출력 3 ``` 66 ``` #### 예제 설명 1 처음 변경에서 1번 고객이 $(1, 1)$을 $(1, 1)$로 고쳐달라고 하기 때문에 실제로 변하는 것은 없고 그림을 판매하는 가능한 경우의 수는 1이다. 유일한 방법은 두 고객에게 둘 다 색깔이 있는 그림을 판매하는 것인데 $C=2$이기 때문에 이러한 방법만 존재할 수 밖에 없다.