给你一个大小为 N 的双端队列 Q，和一个大小为 M 的查询数组 A。

对于每个查询 A[i] = [idx, val]，你要把 Q 里从队头开始数的第 idx 个元素增加 val，然后把 Q 内的所有元素复制到一个新的双端队列 Q2, 保持 Q 内的元素不变, 在这之后你可以对 Q2 执行以下两种操作任意次:

把队头的元素移到队尾，减少 C1 分。
把队尾的元素移到队头，减少 C2 分。

在上面两种操作执行任意次之后，上面两种操作不能再被执行。此时可以执行以下任意两种操作最多 K 次:

把队头的元素 V 弹出，获得 V 分。
把队尾的元素 V 弹出，获得 V 分。

请你对每个查询, 分别输出操作后的最大分数。

第一行有三个正整数 N, M, K，分别代表队列的大小 和 查询的数量 和后两种操作的最大执行次数。

第二行有两个整数 C1, C2，分别代表执行第一种操作减少的分数 和 执行第二种操作减少的分数。

第三行有 N 个整数，第 i 个整数代表队列里从队头开始数的第 i 个元素。

然后有 M 行，每一行有两个整数 idx, val, 代表查询的值。

输出有 M 行，每一行有一个整数，代表操作后最大的分数。

3 2 1
1 1
1 1 1
1 1
2 100

2
100

1 <= N, M <= 100000
1 <= K < N
1 <= C1, C2 <= 1000000000
1 <= Q[i] <= 1000000000
1 <= idx <= N
1 <= val <= 1000000000