Problem Statement

A store sells $N$ items, numbered as item $1$, item $2$, $\ldots$, item $N$. Item $i$ $(1\leq i\leq N)$ has a price of $P_i$ yen and a value of $V_i$. The store has only one stock of each item.

Takahashi chooses some items such that the total price is at most $M$ yen. Here, it is guaranteed that $M$ is at least the price of any item. That is, for any $1\leq i\leq N$, there exists a way to choose items such that the total price is at most $M$ yen and item $i$ is included.

For each $1\leq i\leq N$, determine which of the following three categories item $i$ falls into:

• Category A: To maximize the total value of the chosen items (while keeping the total price at most $M$ yen), that item must be chosen.
• Category B: To maximize the total value of the chosen items (while keeping the total price at most $M$ yen), that item may or may not be chosen.
• Category C: To maximize the total value of the chosen items (while keeping the total price at most $M$ yen), that item must never be chosen.

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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
P_1 V_1
P_2 V_2
\vdots
P_N V_N

Output

Print a string of length $N$ consisting of A, B, and C. If item $i$ $(1\leq i\leq N)$ falls into category $X$ (where $X$ is A, B, or C), the $i$-th character of the output string should be $X$.