Problem G
Chefes Pontuais

Pessoas do mundo todo vão a maravilhosa cidade do Rio de Janeiro para aproveitar o calor, a paisagem e a comida local! Dois privilegiados chefes da região trabalham próximo a praia e disputam o mercado local de food trucks. Eles são Alberto do Sanduba e Bernardo do Hambúrguer. Alberto é mais veloz porém Bernardo é mais caprichoso.

$n$ clientes famintos chegam a praia e avistam os food trucks de Alberto e Bernardo. O $i$-ésimo cliente chega no tempo $t_ i$ e fará um pedido que demorará $d_ i$ para cozinhar se feito por Alberto e $k\cdot d_ i$ se feito por Bernardo.

Como os chefes trabalham sozinhos, ele só atendem o próximo cliente e começam a cozinhar seu pedido quando terminam de cozinhar o pedido anterior. Os clientes vão para o estabelecimento com menos pessoas na fila no momento em que chegam, e depois não trocam de fila. Se ambas as filas têm o mesmo número de clientes, o cliente vai para Alberto.

Se em um mesmo momento um cliente chega e um chefe conclui um pedido (quando então uma pessoa sai de sua fila), considere que a pessoa sai da fila antes da que acabou de chegar tomar a decisão de qual fila entrar. E se dois clientes chegam na área no mesmo momento, considere que o cliente com menor índice escolhe em qual fila entrar antes (clientes são numerados de $1$ a $n$ na ordem em que são lidos no input).

Um investidor da região quer saber como andam os negócios de Alberto e Bernardo para decidir em qual apostar. Dados as informações dos $n$ clientes e o número $k$, o coeficiente de atraso de Bernardo, diga em qual food truck cada cliente irá e em que momento seu pedido fica pronto.

Input

A primeira linha do input contém dois inteiros $n$ e $k$ ($1 \leq n \leq 100\, 000, 2 \leq k \leq 10\, 000$), seguidos de $n$ linhas, cada uma com $t_ i$ e $d_ i$ ($0 \leq t_ i \leq 1\, 000\, 000\, 000, 1 \leq d_ i \leq 1\, 000\, 000\, 000$) o tempo em que o $i$-ésimo cliente chega e o tempo que pedido demorará, caso seja feito por Alberto.

Output

Para cada um dos $n$ clientes, imprima uma linha contendo um caracter ‘A’ se ele fez seu pedido para Alberto ou ‘B’ se foi feito para Bernardo, seguido de $f_ i$, o momento em que seu pedido é finalizado. Para imprimir, mantenha a ordem dos clientes conforme lida no input.

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