题目描述

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

输入描述

第一行输入两个整数$n,q(1 \leq n,q \leq 10^5)$，表示数组的长度和询问的次数

第二行输入$n$个整数$a_i(1\le a_i\le 10^9)$，其中如果输入的$a_i$为$0$，那么说明$a_i$是未知的

接下来的$q$行，每行输入两个正整数$l,r(1 \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$