### 问题描述

有 $n$ 个整数，可能为正数、$0$ 或负数。有 $m$ 次操作，每次操作处理一个区间 $[L_i, R_i]$，使得第 $L_i$个 $\sim$ 第 $R_i$ 个数每个数的符号变反，对 $0$ 而言，符号变反后还是 $0$。数的序号从 $1$ 开始计起。

现在允许任意调整这 $n$ 个数的顺序。问如何调整数的顺序后，使得 $m$ 次操作后这 $n$ 个数之和达到最大，以及如何调整数的顺序后，使得 $m$ 次操作后这 $n$ 个数之和达到最小。

输入格式

输入数据第一行为两个整数 $n$ 和 $m$，$1\le n, m\le 10^5$，分别表示数的个数和操作的次数。

第二行为 $n$ 个整数，这 $n$ 个整数均不超过 int 型范围。

接下来有 $m$ 行，每行为两个正整数 $L_i, R_i$，$1\le L_i\le R_i\le n$，表示一次操作的区间。

输出格式

输出两个整数，表示调整 $n$ 个整数的顺序，执行 $m$ 次操作后，$n$ 个数之和的最大值和最小值，用空格隔开。

样例输入

5 2
-9 20 -27 13 129
1 3
2 5

样例输出

172 -198