# 世纪轰炸机

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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

### 输入

```text
5 1 1 5
1 2 3 4 5
1
1 1
2 2
3 3
4 4
5 5
```

### 输出

```text
15
```

### 解释

五次投送分别选择一名士兵，唯一位置收到 $1+2+3+4+5=15$ 份补给。

## 样例 2

### 输入

```text
4 5 2 2
1 2 3 4
1 4
2 4
1 2
```

### 输出

```text
3 5 4 3 5
```

### 解释

从任一起点算起，偏移为 $0,1,2$ 的补给合计分别为 $3,5,4$ .将这一序列分别从位置 $1$ 和 $4$ 开始累加；第二份中超出位置 $5$ 的部分忽略。

## 样例 3

### 输入

```text
1 3 0 0
9

```

### 输出

```text
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% | 无额外条件 |