配点: 5 点
問題文
在高桥屋百货公司,
首次销售将持续N 天。
在
i (1 \leq i \leq N) 日,A_i 日元福袋A和 B_i 日元福袋B将被出售。
高桥君是 N 我每天都会去高桥屋买福袋A或福袋B。(你不能不买任何东西。)
在
N 天内购买 N 福袋总数正好是 S 我想用日元购买。
由于高桥君不擅长算计,所以你应该代他制定购买符合条件的福袋的计划。
如果没有此类购买计划,请报告。
制約
- 1 \leq N \leq 100
- 1 \leq S \leq 10^5
- 1 \leq A_i, B_i \leq 10^5 (1 \leq i \leq N)
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N S A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
计划满足问题陈述中的条件的购买如下。 请将其输出为 N 字符串 T 。
- i (1 \leq i \leq N) 如果您在 T_i=
'A',如果您想购买福袋B, T_i='B'
如果没有符合条件的采购计划。 'Impossible' 。
入力例 1
3 34 3 14 15 9 26 5
出力例 1
BAB
如果您按以下方式购买,则总金额将为 14+15+5=34 是日元。
- 1 当天的福袋B(14 円)
- 2 当天福袋A(15 円)
- 3 当天的福袋B(5 円)
入力例 2
5 77 1 16 3 91 43 9 4 26 23 11
出力例 2
BABBA
如果您这样购买,总金额将为 16+3+9+26+23=77 是日元。
除此之外,BAAAB 但总金额是 16+3+43+4+11=77 答案是日元,所以答案是正确的。
入力例 3
5 59 8 13 55 5 58 8 23 14 4 61
出力例 3
Impossible
可能没有满足条件的购买方式。