题目描述

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

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

当然，这道题只涉及减法，于是鸡尾酒还有一道同样的题目（只有加粗的地方不同）：给定一个包含 $𝑛$ 个数字的数组，每次你可以任选两个数字做求余运算，将这两个数字变成一个新数字放回数组，经过 $𝑛−1$ 次操作之后变成一个数字。你的目标是让最终的这一个数字变得尽可能大，请问最大是多少。

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

看来丹丹又分不清了，你能帮帮他吗？为了防止丹丹搞混数字，所以鸡尾酒给出的 $𝑛$ 个数字各不相同。

输入格式

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

接下来一行输入 $𝑛$ 个数字，其中第 $𝑖$ 个数字为 $a_i\ (1 ≤ a_i ≤ 10^6)$。

输出格式

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

5 1
1 2 3 4 5

13

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

3 2
100 400 905

100

$𝑘=2$，说明是一道求余问题，先用 $905$ 求余 $400$，得到余数 $505$，然后用 $100$ 求余 $505$，得到余数 $100$。方案不唯一，但是无法得到比 $100$ 还大的数字了。