Universal Cup你的面前有 $n$ 张卡牌，从左往右数第 $i$ 张上面写着一个正整数 $A_i$。
你将会拿出其中的若干张，保持它们的相对顺序不变，形成一个新的卡牌序列。
不妨设这个新的卡牌序列有 $m$ 张牌，第 $i$ 张上写的数是 $B_i$。
定义这个卡牌序列的价值是：
$$ \sum \limits_{i=1}^{m-1}\lfloor \frac{S}{\textbf{LCM}(B_i,B_{i + 1})}\rfloor \times \textbf{LCM}(B_i,B_{i + 1}) $$
其中 $\textbf{LCM}(x,y)$ 表示 $x$ 和 $y$ 的最小公倍数。
请最大化价值。
对于一些数据，你还需要解决如下问题：
增加禁用规则，如果第 $i$ 张牌被禁用，你拿出的卡牌序列不可以包含它。
你想知道：对于 $i=1...n$，它被禁用后，你可以拿出的卡牌序列的价值最大是多少，设为 $ans_i$。
为了减少输出量，你只需输出 $\bigoplus\limits_{i=1}^ni\times ans_i$。
输入格式
第一行四个正整数 $n,S,tp,id$，前两个参数如上所示， $tp=0/1$ 表示该数据的类型（详见输出格式）， $id$ 表示子任务编号。
第二行 $n$ 个正整数 $A_1...A_n$。
输出格式
- 若 $tp=0$，输出一行一个整数，表示无禁用规则的答案。
- 若 $tp=1$，输出一行两个整数，分别表示表示无禁用规则的答案和禁用规则下的 $\bigoplus\limits_{i=1}^ni\times ans_i$。
样例数据
样例 1 输入
5 10 1 1
3 2 1 4 5样例 1 输出
26 18样例 2 输入
10 9999 1 1
93 120 538 410 1 248 100 11 45 14样例 2 输出
72490 231470数据范围与约定
| 子任务编号 | 分值 | $n\le$ | $S\le$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $5$ | $10^3$ | $10^5$ | 无 |
| $2$ | $5$ | $10^4$ | ||
| $3$ | $10$ | $10^5$ | $3 \times 10^5$ | $A_i$ 在 $[1, S]$ 中均匀随机 |
| $4$ | $10$ | $A_i \le 100$ | ||
| $5$ | $10$ | $10^5$ | $tp = 0$ | |
| $6$ | $10$ | 无 | ||
| $7$ | $10$ | $3 \times 10^5$ | $3 \times 10^5$ | $tp = 0$ |
| $8$ | $10$ | 无 | ||
| $9$ | $15$ | $5 \times 10^5$ | $5 \times 10^5$ | $tp = 0$ |
| $10$ | $15$ | 无 |
对于所有数据，$1\le A_i\le 10^9$。