世纪轰炸机¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：8 MB
背景故事¶
盟军正在用世纪轰炸机演练物资投送。不同士兵携带的补给数量不同，每个机组选择一段连续编号的士兵，并在所有指定起点各投送一份同样的队列。请统计演练结束后战线上各位置收到的补给。
形式化问题描述¶
给定长度为 \(n\) 的序列 \(a\) ，长度为 \(m\) 的战线，以及 \(k\) 个互不相同的起点 \(p_1,\ldots,p_k\) .战线位置编号为 \(1\) 到 \(m\) ，初始补给均为零。
每次投送给出区间 \([l,r]\) .对每个起点 \(p_i\) 及每个 \(0\le j\le r-l\) ，若 \(p_i+j\le m\) ，就在位置 \(p_i+j\) 增加 \(a_{l+j}\) 份补给。超出战线的位置忽略。不同投送、不同起点的贡献都要相加；序列 \(a\) 不会改变。
完成全部 \(q\) 次投送后，输出每个位置的补给总量。
输入格式¶
第一行四个整数 \(n,m,k,q\) .第二行 \(n\) 个整数 \(a_i\) .第三行 \(k\) 个整数 \(p_i\) ；当 \(k=0\) 时这一行为空。接下来 \(q\) 行，每行两个整数 \(l,r\) .
输出格式¶
输出一行 \(m\) 个整数，依次表示位置 \(1\) 到 \(m\) 的补给总量。
样例 1¶
输入¶
5 1 1 5
1 2 3 4 5
1
1 1
2 2
3 3
4 4
5 5
输出¶
15
解释¶
五次投送分别选择一名士兵，唯一位置收到 \(1+2+3+4+5=15\) 份补给。
样例 2¶
输入¶
4 5 2 2
1 2 3 4
1 4
2 4
1 2
输出¶
3 5 4 3 5
解释¶
从任一起点算起，偏移为 \(0,1,2\) 的补给合计分别为 \(3,5,4\) .将这一序列分别从位置 \(1\) 和 \(4\) 开始累加；第二份中超出位置 \(5\) 的部分忽略。
样例 3¶
输入¶
1 3 0 0
9
输出¶
0 0 0
解释¶
没有投送起点，也没有投送操作，所有位置的补给均为零。
数据范围与保证¶
- \(1\le n,m\le2000\) ，\(0\le k\le m\) ，\(0\le q\le30000\) .
- \(0\le a_i\le9\) ，\(1\le p_i\le m\) ，所有 \(p_i\) 互不相同。
- 每次投送满足 \(1\le l\le r\le n\) .
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |