题目描述

塔子哥拿到了一个由正整数组成的数组，但其中有一些元素是未知的(用0来表示)。现在塔子哥想知道，如果那些未知的元素在区间$[l,r]$范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少?共有q次润问。

输入描述

第一行整数$n$和$q$，表示数组的长度和询问的次数

第二行输入$n$个整数$a_i$，其中如果输入的$a_i$为$0$，那么说明$a_i$是未知的 接下来的$q$行，每行输入两个正整数$l,r$，代表一次询问。

$1 \leq n,q \leq 10^5$

$0 \leq a_i \leq 10^9$

$l \le l\le r \le 10^9$

输出描述

输出$q$行，每行输出两个正整数，代表所有元素之和的最小值和最大值.

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3 2
3 0 2
1 1
1 2

输出

6 6
6 7

说明

第二次询问中，最小为$1+2+3=6$，最大为$2+2+3=7$