Description

鸡尾酒的学生丹丹永远分不清减法和求余，他觉得两种运算都是将数字变小，所以差不多。 于是鸡尾酒给了他两道题目来帮助他分清这两种运算。第一道题目是这样的： 给定一个包含 n 个数字的数组， 每次你可以任选两个数字做减法运算，将这两个数字变成一个新数字放回 数组，经过 n − 1 次操作之后变成一个数字。你的目标是让最终的这一个数字变得尽可能 大，请问最大是多少。 当然，这道题只涉及减法，于是鸡尾酒还有一道同样的题目(只有加粗的地方不同)：给定 一个包含 n 个数字的数组， 每次你可以任选两个数字做求余运算， 将这两个数字变成一个 新数字放回数组，经过 n − 1 次操作之后变成一个数字。你的目标是让最终的这一个数字 变得尽可能大，请问最大是多少。

丹丹说：“都是 n 个数字变成 1 个数字，这两道题不是一样吗？ ” 看来丹丹又分不清了，你能帮帮他吗？

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

Input Format

第一行输入一个正整数 n, k， 表示共有 n 个数字， k 是题目编号， 如果 k = 1， 则你需要 完成“减法”这道题， k = 2 表示你需要完成“求余”这道题。 接下来一行输入 n 个数字，其中第 i 个数字为 $ai (1 ≤ ai ≤ 10^6)$

Output Format

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

5 1
1 2 3 4 5

13

3 2
100 400 905

100

Hint

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

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