题目背景

$Zero$ 和 $Mike$是一对热爱旅行的好朋友，一天在经历了$ZXG$大神的历练后，心力交瘁，于是决定重阳节回宾馆刷题，找回自信，于是，我们的故事开始了……

题目描述

出题人：各位 $Oier$ 一定要细心啊啊啊！！！注意看说明

出题人：Chen_Xi.Naoh

$Zero$ 所在宾馆的房间号是 $703$ ，而 $Mike$ 所在宾馆的房间好却是 $704$ ，所以当 $Zero$ 和 $Mike$ 想凑在一起刷题的时候，$Zero$ 需要从 $703$ 前往 $704$ 或者 $Mike$ 从 $704$ 前往 $703$ ，当 $Zero$ 和 $Mike$ 凑在一起时，$Mike$ 便会从 $luogu$ 上随机选择 $n$ 道题，每一道题分值为 $300$ ，由于 $Mike$ 身经百战，所以每当 $Mike$ 看到某道题目的时候，大脑里面就会自动给该到题目定义一个难度值 $hard$ (要相信 $Mike$ 的判断都是正确的)，而 $Zero$ 和 $Mike$ 两个人都有一个共同的天赋值 $Talent$ ,每个人都只能解出 $Talent$ 范围内难度的题目，当然 $Zero$ 和 $Mike$ 的天赋值不会很低；

在 $Zero$ 的房间 $703$ 里面有一位热爱学习的小学弟 $BookCity$ ，在 $Zero$ 和 $Mike$ 刷题的同时，$BookCity$ 会在一旁研究两位学长的做题习惯，并给两位学长加油助威，由于 $BookCity$ 的加油，某道题目的难度就会自动下降一点点(若 $hard - d \le 0$，则默认该题的 $hard$ 为 $1$ )；然而，在宾馆的 $123$ 号房间住着一个拥有魔法但心地邪恶的人 $Guy$ ，能够看到Zero和Mike的动静，并且能够施展魔法(因为是在重阳节)，在 $Zero$ 和 $Mike$ 做到某一题的时候，直接将该题的难度暴增至 $s$ 倍！！！！！幸运的是，$Zero$ 和 $Mike$ 的老师 $tingtime$ 会帮助他们两个，在困境的时候为 $Zero$ 和 $Mike$ 指点迷津，将某一题的难度直接调为一个很低的值。

$Zero$ 和 $Mike$ 每刷完一道题能获得对应分值的自信值( $Zero$ 和 $Mike$ 都是追求完美的人，每一道题要么对，要么干脆不写)，现在，你就是 $Zero$ ，你想知道如果和 $Mike$ 从第 $a$ 到题刷到第 $b$ 到题能回复多少自信值 (自信值计算方法：$600*AC$ 题目个数 $\Longrightarrow$ 一道题 $300$ 分，$2$ 个人一共恢复 $600$ 自信值)$Confidence$。

输入格式

第一行输入两个数，分别表示题目个数 $n$ 和天赋值 $Talent$。
第二行将输入 $n$ 个数，第 $i$ 个数表示第 $i$ 题的 $hard$ 值。
第三行，输入一个数表示事件个数 $m$ ， 接下来的 $m$ 行中，每行一个合题意事件，严格保证所有事件按顺序发生。

输出格式

对于 $Zero$ 的每个询问，输出一行，回答他和 $Mike$（两个人） 能够获得的最大值$Confidence$。

5 5
2 3 4 5 9
5 
BookCity 1 1
Guy 2 5
Zero 1 5
tingtime 5 1
Zero 1 5

1800
2400

提示

保证所有题目初始的难度值 $hard$ 在 $[0,2^{31}-1]$ 范围内；

保证 $Zero$ 和 $Mike$ 的天赋值 $Talent$ 在 $[0,2^{31}-1]$ 范围内；

保证 $Zero$ 询问的范围都在 $[0,2^{31}-1]$ 范围内，但不保证$x$一定会小于$y$

保证 $Guy$ 的翻倍都在 $[0,2^{31}-1]$ 范围内；

保证 $BookCity$ 的减小值 $d$ 都在 $[0,2^{31}-1]$ 范围内；

保证所有的输入数据都在 $[0,2^{31}-1]$ 范围内；

$Mike$ 身经百战，所以其判断的 $hard$ 都在 $[0,2^{31}-1]$ 范围内，且不存在难度为负数或者为 $0$ 的送分题；

保证 $n$ 和$m$ 都在 $[0,2^{31}-1]$ 范围内；

对于 $30\%$ 的数据：$0\leqslant n \leqslant 5\times 10^3$,$m \leqslant 5\times 10^3$；

对于 $50\%$ 的数据：$0\leqslant n \leqslant 5\times 10^4$,$m \leqslant 5\times 10^4$；

对于 $100\%$ 的数据：$0\leqslant n\leqslant 5\times 10^5$，$m\leqslant 5\times 10^5$。

** 总之保证所有输入数据在$[0,2^{31}-1]$范围内，但不保证运算在$[0,2^{63}-1]$范围内！！**