题目描述

小博的学生Sheryang永远分不清减法和求余，他觉得两种运算都是将数字变小，所以差不多。

于是小博给了他两道题目来帮助他分清这两种运算。第一道题目是这样的：给定一个包含$n$个数字的数组，每次他可以任选两个数字做减法运算，将这两个数字变成一个新数字放回数组，经过$n-1$次操作之后变成一个数字。题的目标是让最终的这一个数字变得尽可能大，请问最大是多少。

当然，这道题只涉及减法，于是小博还有一道同样的题目：给定一个包含$n$个数字的数组，每次他可以任选两个数字做求余运算，将这两个数字变成一个新数字放回数组，经过$n-1$次操作之后变成一个数字。他的目标是让最终的这一个数字变得尽可能大，请问最大是多少。

Sheryang说：“都是$n$个数字变成$1$个数字，这两道题不是一样吗？”

看来Sheryang又分不清了，你能帮帮他吗？

为了防止Sheryang搞混数字，所以小博给出的𝑛个数字各不相同。

输入格式

第一行输入一个正整数$n,𝑘$，表示共有$n$个数字，$k$是题目编号，如果$k= 1$，则你需要完成“减法”这道题，$k=2$表示你需要完成“求余”这道题。

接下来一行输入$n$个数字，其中第$i$个数字为$a_i$

输出格式

输出一行一个整数表示答案

5 1
1 2 3 4 5

13

3 2
100 400 905

100

样例说明

样例1的 $k = 1$，说明是一道减法问题，可以先用数组中的1减去2，得到-1，然后用-1减去4，得到-5，用-5减去5，得到−10，用3减去-10，得到13。

样例2的$𝑘= 2$，说明是一道求余问题，先用$905$求余400，得到余数105，然后用100

求余105，得到余数100。方案不唯一，但是无法得到比100还大的数字了。

数据范围

$60\%$的数据满足, $1\le n \le 3，1\le k \le 2，1\le a_i \le 10^6$

$100\%$的数据满足, $1\le n \le 10^5，1\le k \le 2,1\le a_i \le 10^6$