g5-09203. 两种装法 未做

同一批 $n$ 箱货按单号 $1$ 到 $n$ 排好，第 $i$ 箱重量为 $w_i$，装箱上限为 $cap$。用两种装法各装一遍，每装法从空箱开始：
装法一从第 $1$ 箱货开始从左往右扫描，能装进当前箱就装入（装入后箱内总重不超过 $cap$），装不下就封箱并另开新箱；
装法二从第 $n$ 箱货开始从右往左扫描，规则相同，能装就装，装不下封箱另开新箱。
第一行按开箱顺序输出装法一各箱总重；第二行按开箱顺序输出装法二各箱总重；第三行：若前两行完全相同输出 SAME，否则输出 DIFF。数据保证 $cap$ 不小于任何单箱重量。

第一行两个整数 $n,cap$。
第二行 $n$ 个整数 $w_1,w_2,\dots ,w_n$，按单号顺序给出。

共三行：第一行为装法一各箱总重，第二行为装法二各箱总重（各箱总重均按开箱顺序、以空格分隔），第三行为 SAME 或 DIFF。

装法一：箱 $1$ 装 $2+4=6$，再装 $1$ 到 $7$ 超出，封箱；箱 $2$ 装 $1+3=4$，再装 $5$ 到 $9$ 超出，封箱；箱 $3$ 装 $5$，再装 $2$ 到 $7$ 超出，封箱；箱 $4$ 装 $2$，总重依次 $6,4,5,2$。装法二从最右往左：箱 $1$ 装 $2$，再装 $5$ 到 $7$ 超出，封箱；箱 $2$ 装 $5$，再装 $3$ 到 $8$ 超出，封箱；箱 $3$ 装 $3+1=4$，再装 $4$ 到 $8$ 超出，封箱；箱 $4$ 装 $4+2=6$，总重依次 $2,5,4,6$。两行不同，输出 DIFF。

• $1\le n\le 2\times 10^5$；
• $1\le w_i\le 10^9$，$1\le cap\le 10^9$，保证 $cap\ge \max w_i$。