题目描述

小缘做了一下NOIP2004的合并果子，二十年过去了，她觉得这个题目有些过时，所以她把题目换了一个思路问你。

给你一个长度为 $n$ 的整数数组 $a_i$，保证数组中的数互不相同，每次给定操作类型 $\it op$。

若 ${\it op} = 1$，则每次从数组中任选两个数 $a_i,a_j$，把这两个数从数组中删除，并将这两个数的差 $a_i-a_j$ 放入数组。

若 ${\it op} = 2$，则每次从数组中任选两个数 $a_i,a_j$，把这两个数从数组中删除，并将这两个数做除法的余数 $a_i\%a_j$ 放入数组。

显然经过 $n-1$ 次操作后，数组中只剩下 $1$ 个数。你需要告诉她，这个剩下的数最大是多少。

输入格式

第一行两个整数 $n,op$，表示数组长度和操作类型。

第二行 $n$ 个整数 $a_1,\cdots, a_n$。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

5 1
5 3 4 2 1

样例输出 #1

13

样例 #2

样例输入 #2

3 2
905 100 400

样例输出 #2

100

提示

$1\le a_i\le 10^6$.