Problem G
Punctual Chefs

People from all over the world go to the wonderful city of Rio de Janeiro to enjoy the heat of the summer, the scenery and the local food! Two great chefs from the region work near the beach and compete for the control of the local food truck market. They are Alberto of the Sanduba and Bernardo of the Burger. Alberto is faster but Bernardo has better food.

$n$ hungry clients will arrive at the beach and see the food trucks of Alberto and Bernardo. The $i$-th customer arrives at time $t_ i$ and will make an order that will take $d_ i$ seconds to be cooked by Alberto and $k\cdot d_ i$ by Bernardo.

Because the chefs work alone, they will only start cooking the order of the next customer when they finish cooking the previous order. While the chef is cooking, the costumers wait patiently on line. Clients go to the establishment in which the queue has fewest people at the moment they arrived and then do not change queues. If both queues have the same number of customers, the customer goes to Alberto.

If a customer arrives and a chef completes an order at the same time, consider that the person leaves the queue before the person who has just arrived makes the decision of which queue to enter. And if two clients arrive in the area at the same time, consider that the client with the lowest index chooses which queue to enter before (clients are numbered from $1$ to $n$ in the order they are read in the input).

A local investor wants to know which business they are going to put their money in. Please let them know at which food truck each costumer will be served and at what time their order will be ready.

Input

The first line of the input contains two integers $n$ and $k$ ($1 \leq n \leq 100\, 000, 2 \leq k \leq 10\, 000$), followed by $n$ lines, each with $t_ i$ and $d_ i$ ($0 \leq t_ i \leq 1\, 000\, 000\, 000, 1 \leq d_ i \leq 1\, 000\, 000\, 000$) the time the $i$-th customer arrives and the time Alberto will take to cook the $i-th$ order.

Output

For each of the $n$ customers, print a line containing a character ‘A’ if he placed his order for Alberto or ‘B’ if it was made for Bernardo, followed by $f_ i$, the time his order is finalized. Keep the order of the customers as read in the input to print the answer.

4 2
0 10
6 6
1 5
10 1

A 10
A 16
B 11
A 17

4 2
0 10
6 6
1 5
9 1

A 10
A 16
B 11
B 13

3 10
0 1
0 1
0 1

A 1
B 10
A 2