D-「SFCOI-4」丰饶的小镇

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小 S 有一个长度为 $n$ 的排列 $p$ 。他感到无聊，于是进行了这样的思想实验：按原序取出下标从 $l$ 到 $r$ 的元素，得到长度为 $n' = r - l + 1$ 的子序列 $p'$ 。
$\hspace{15pt}$ 他构想这样得到的子序列是小镇上的一条街道，在这条街道的 $n'$ 栋建筑中居住着许多人，初始第 $i$ 栋建筑中有 $2^{p'_i}$ 个人。
$\hspace{15pt}$ 在每一秒内，这条街道上的人都会搬一次家，他们都会同时搬到相邻（如果存在）且人数最多的建筑中，不可以停留在原建筑不搬家；若相邻建筑中人数相同，则可任选一侧。
$\hspace{15pt}$ 在 $10^{114514^{1919810}}$ 秒后，设第 $i$ 栋建筑中有 $a_i$ 个人。小 S 给出每一栋建筑的重要性序列 $c$ ，并定义整个小镇的「丰饶度」为：

$\displaystyle\sum_{i = 1}^{n'} \Big( c_{i + l - 1} \times \big\lfloor \log_2 \max(a_i, 1) \big\rfloor \Big)$

$\hspace{15pt}$ 他一共进行了 $q$ 次思想实验，每次实验均基于原排列 $p$ 独立进行，互不影响。对于每一次实验，请你告诉小 S 这座小镇最后的「丰饶度」。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

第一行输入两个整数 ，表示建筑数量、思想实验次数。
第二行输入  个两两不同的整数 ，表示排列 。
第三行输入  个整数 ，表示小镇上第  栋建筑的重要性。
此后  行，第  行输入两个整数 ，表示第  次思想实验的区间。

输出描述:

对于每一次思想实验，新起一行输出一个整数，表示小镇最后的「丰饶度」。

示例1

输入

复制

8 2
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
2 7
1 8

输出

复制

32
22

说明

对于第一次思想实验，起初各建筑中的人数依次为 ：
 秒后，各建筑中的人数依次为 ；
 秒后，各建筑中的人数依次为 ；
 秒后，各建筑中的人数依次为 ；
 秒后，各建筑中的人数依次为 ；
 秒后，各建筑中的人数依次为 ；
；
 秒后，各建筑中的人数依次为 。
因此，该实验的答案为 。