Background

小笨蛋学生总是分不清减法和求余，他觉得两种运算都是将数字变小，所以差不多。

于是你出了两道课前测来帮助他分清这两种运算：

• 减法题：给定包含n个数字的数组，每次可以任选两个数字做减法运算，变成一个新数字并放回数组，经过 $n-1$ 次操作后变成一个数字，你的目标是让最终的这个数字变得尽可能大，请问最大是多少。
• 求余题：给定包含n个数字的数组，每次可以任选两个数字做求余运算，变成一个新数字并放回数组，经过 $n-1$ 次操作后变成一个数字，你的目标是让最终的这个数字变得尽可能大，请问最大是多少。

Format

Input

第一行输入两个正整数n，k，表示有n个数字，k是题目编号。

如果k=1，则你需要完成减法题，若k=2，则你需要完成求余题。

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

Output

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

Samples

5 1
1 2 3 4 5

13

3 2
100 400 905

100

样例1解释

先用 1 减去 2，得到 -1，然后 -1 减去 4 得到 -5， 用 -5 减去 5 得到 -10，用 3 减去 -10 得到 13.

Limitation

保证所有数字均为互不相同的正整数，且不超过1e9