题目描述

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

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

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

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

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

为了防止丹丹搞混数字，所以鸡尾酒给出的 $𝑛$ 个数字各不相同。

输入格式

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

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

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

5 1
1 2 3 4 5

3 2
100 400 905

【样例一说明】

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

【样例二说明】

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

【数据范围】