AT_abc441_f [ABC441F] Must Buy

ある店に $ N $ 個の商品が売られており、商品 $ 1 $ , 商品 $ 2 $ , $ \ldots $ , 商品 $ N $ と番号づけられています。 商品 $ i $ $ (1\leq i\leq N) $ の値段は $ P_i $ 円で、価値は $ V_i $ です。どの商品も $ 1 $ つずつしか存在しません。 高橋君は、値段の合計が $ M $ 円以下となる範囲でいくつかの商品を選びます。 ここで、 $ M $ は任意の商品の値段以上であることが保証されます。 すなわち、任意の $ 1\leq i\leq N $ について、値段の合計が $ M $ 円以下となる選び方であって商品 $ i $ を含むようなものが必ず存在します。 このとき、 $ 1\leq i\leq N $ それぞれについて、商品 $ i $ が以下の $ 3 $ つの分類のどれに該当するか判定してください。 - 分類 A: （値段の合計が $ M $ 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を必ず選ばなければならない。 - 分類 B: （値段の合計が $ M $ 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を選んでも選ばなくてもよい。 - 分類 C: （値段の合計が $ M $ 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を決して選んではならない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ P_1 $ $ V_1 $ $ P_2 $ $ V_2 $ $ \vdots $ $ P_N $ $ V_N $

`A`,`B`,`C` からなる長さ $ N $ の文字列を出力せよ。 商品 $ i $ $ (1\leq i\leq N) $ が分類 $ X $ （ $ X $ は A,B,C のいずれか）に該当するとき、出力する文字列の $ i $ 文字目が $ X $ となるようにせよ。

### Sample Explanation 1 値段の合計が $ 7 $ 円以下となる範囲で商品を選んだ時の価値の合計としてあり得る最大値は $ 30 $ であり、これは - 商品 $ 1 $ と商品 $ 2 $ と商品 $ 5 $ を選ぶ。 - 商品 $ 4 $ と商品 $ 5 $ を選ぶ。 のいずれかによって達成できます。（これ以外に値段の合計が $ 7 $ 円以下かつ価値の合計が $ 30 $ となる選び方はありません。） これより、各商品の分類は次のようになります。 - 商品 $ 5 $ は、選んだ商品の価値の合計を最大にするには、必ず選ばなければならない商品（分類 A ）です。 - 商品 $ 1 $ , 商品 $ 2 $ , 商品 $ 4 $ は、選んだ商品の価値の合計を最大にするために、選んでも選ばなくてもよい商品（分類 B ）です。 - 商品 $ 3 $ は、選んだ商品の価値の合計を最大にするには、決して選んではならない商品（分類 C ）です。 よって、出力形式に従って、`BBCBA` を出力します。 ### Sample Explanation 2 商品 $ 3 $ , 商品 $ 4 $ , 商品 $ 5 $ のうちいずれか $ 1 $ つと、商品 $ 6 $ , 商品 $ 7 $ を選んだ時に価値の合計が最大となります。 値段と価値がともに等しい商品であっても、商品としては区別されることに注意してください。 ### Constraints - $ 1\leq N\leq 1000 $ - $ 1\leq M\leq 5\times 10^4 $ - $ 1\leq P_i\leq M $ - $ 1\leq V_i\leq 10^9 $ - 入力はすべて整数