페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2980

미술품 판매상(RELATIVNOST) 4초 32MB

문제

경원이는 미술품 판매상이다. N명의 단골 고객을 확보하고 있으며 고객들에게 미술품을 판매한다. 

각 고객은 컬러 그림(들)이나 흑백그림(들) 중 한 종류를 구매한다. 두 종류를 한꺼번에 구매 하지는 않는다. 

k번째 고객은 많아야 ak개의 컬러 그림이나 많아야 bk개의 흑백 그림을 구매하기를 원한다.

 

경원이는 각 고객에 대하여 적어도 하나의 그림은 반드시 받을 수 있도록 판매한다. 

또한 거의 무한대의 그림을 보유하고 있어 고객들이 주문하는 개수를 모두 충족시킬 수 있다.

 

경원이는 흑백그림보다는 컬러 그림 판매를 좋아하는 편이다. 그래서 고객들 중에 C명 이상의 고객이 컬러 그림을 구입하기를 원한다.

 

그런데 경원이의 고객들은 지속적으로 희망하는 그림의 주문 개수를 바꾼다. 

그때 마다 경원이는 “적어도 C명 이상의 고객이 컬러그림을 구입하는 경우의 수는 얼마나 될 까?” 하는 의문이 생겼다.

 

경원이를 도와 궁금함을 해결해 주자. 경원이가 판매하는 컬러 그림은 모두 같은 그림이며 흑백 그림도 모두 같은 그림이다.

따라서 경원이가 관심을 두는 것은 컬러인지 아닌지와 각 고객이 구입하는 그림의 개수이다.

 

입력 예 2를 보면

1 2 2 로 첫 번째 고객의 주문이 컬러 2개 흑백 2개로 바뀌었다. 따라서

첫 번째 고객이 구입하는 컬러 그림을 C1, 두 번째 고객이 구입하는 컬러 그림을 C2라고 할 때

(C1, C2) 쌍의 개수는 (1, 1), (1, 2), (2, 1), (2, 2) 가 되어 4가지가 된다.

 

2 2 2 로 두 번째 고객의 주문이 컬러 2개 흑백 2개로 바뀌었다. 컬러 그림의 개수는 변동이 없으므로

(C1, C2) 쌍의 개수는 (1, 1), (1, 2), (2, 1), (2, 2) 가 되어 4가지가 된다.

  


입력

첫 행에 두 개의 정수 N, C(1 ≤ N ≤ 100,000, 1 ≤ C ≤ 20)가 입력된다. 두 번째 행에 N개의 ai(i번째 고객이 구입하기 원하는 컬러그림 개수)가 공백으로 구분되어 입력된다. (1 ≤ ai ≤ 1,000,000,000) 세 번째 행에 N개의 bi(i번째 고객이 구입하기 원하는 흑백그림 개수)가 공백으로 구분되어 입력된다. (1 ≤ bi ≤ 1,000,000,000) 네 번째 행에 변경요청 수 Q (1 ≤ Q ≤ 100,000)가 입력된다. 다음 행부터 Q개의 행에 걸쳐 각 행마다 3개의 정수 P, ap, bp가 공백으로 구분하여 입력된다. P는 변경을 요청한 고객 번호이고 ap는 구입하려는 컬러 그림수, bp는 구입하려는 흑백 그림수이다. (1 ≤ P ≤ N), (1 ≤ ap ≤ 1,000,000,000), (1 ≤ bp ≤ 1,000,000,000)

출력

출력은 Q개의 행으로 구성된다. 각 변경 요청을 적용할 때 마다 가능한 서로다른 구입방법을 구하여 10,007로 나눈 나머지를 행으로 구분하여 출력한다.

예제1

입력
22

11

11

1

111
출력
1

예제2

입력
22

12

23

2

122

222
출력
4

4

예제3

입력
42

1234

1234

1

411
출력
66

출처

COCI 2015/2016 contest1 5

역링크