1349: RELATIVNOST

内存限制:128 MB 时间限制:2.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:34 通过:7

题目描述

Young Luka是个艺术商人,他有N个客户,要卖画给每个客户。

每个客户能买彩色画或者黑白画,必须买其中一种,不能都买。

第i个客户想要至多买ai幅彩色画,或者bi幅黑白画。

Luka不喜欢黑白画,如果少于c个人买彩色画,他会很难过。

他的客户们经常改变需求,也就是说,aibi是会变的。因此,Luka经常被这个问题困扰:“至少c人买彩色画,一共有多少种购买?”请帮助Luka解决他的问题

输入格式

第一行两个整数NCN<=100000,C<=20

第二行N个整数ai(ai<=1000000000)

第三行N个整数bibi<=1000000000

第四行一个整数,修改的次数QQ<=100000

接下来Q行,每行三个整数p,ap,bp(1<=p<=n),表示第p个人至多买的彩色画,黑白画。

30%的数据:N,Q<=1000

输出格式

有Q行,每行一个整数,答案模10007

输入样例 复制

4 2
1 2 3 4
1 2 3 4
1
4 1 1

输出样例 复制

66

分类标签