← 返回题目列表

Codeforces · 534/C

C. 波利卡普斯的骰子

中文机器翻译题面 查看原题

Polycarp 有 n 个骰子 d1, d2, ..., dn。第 i 个骰子显示从 1 到 di 的数字。波利卡普掷了所有骰子,它们显示的数字之和是 A。阿格里皮娜没有看到哪个骰子显示了什么数字,她只知道总和 A 以及值 d1、d2、...、dn。然而,她发现做出一系列以下类型的陈述就足够了:骰子,我无法显示数字 r。例如,如果波利卡普有两个六面骰子,总和为 A = 11,那么阿格里皮娜可以说这两个骰子中的每一个都不能显示小于 5 的值(否则,其余骰子的值必须至少为 7,这是不可能的)。

对于每个骰子,找到可以保证在显示值之和为 A 时骰子不会显示这些值的值的数量。

输入

第一行包含两个整数 n, A (1 ≤ n ≤ 2·105, n ≤ A ≤ s) — 骰子数量以及显示值的总和,其中 s = d1 + d2 + ... + dn。

第二行包含 n 个整数 d1, d2, ..., dn (1 ≤ di ≤ 106),其中 di 是第 i 个骰子可以显示的最大值。

输出

打印 n 个整数 b1, b2, ..., bn,其中 bi 是保证第 i 个骰子无法显示的值的数量。

示例

输入 #1

2 8
4 4

输出 #1

3 3

输入 #2

1 3
5

输出 #2

4

输入 #3

2 3
2 3

输出 #3

0 1

注意

在语句的第一个样本中,只有当第一个和第二个骰子都显示为 4 时,才能获得等于 8 的值。相应地,两个骰子都不能显示值 1、2 或 3。

在语句 A 的第二个示例中,当单个骰子显示 3 时,可以得到等于 3 的值。相应地,它不能显示 1、2、4 或 5。

在语句 A 的第三个示例中,当一个骰子显示 1,另一个骰子显示 2 时,可以获得等于 3 的值。这就是为什么第一个骰子没有任何无法显示的值,而第二个骰子也无法显示 3。