У Алисы и Боба есть доска из \(n\) строк и \(m\) столбцов. В каждой строке есть ровно одна фишка.
Алиса и Боб играют в следующую игру. Они выбирают два целых числа \(l\) и \(r\), такие, что \(1 \le l \le r \le m\), и разрезают доску таким образом, что только столбцы с \(l\) по \(r\) (включительно) принадлежат доски. То есть все столбцы левее столбца \(l\) и все столбцы правее столбца \(r\) больше не являются частью доски.
После разрезания доски они начинают свою игру на оставшейся части доски (от столбца \(l\) до столбца \(r\)). Они ходят по очереди, и первый игрок, который не может сделать ход, проигрывает. Первый ход делает Алиса, второй — Боб, третий — снова Алиса, и так далее. Во время своего хода игрок должен выбрать одну из фишек и сдвинуть ее на любое количество столбцов влево (то есть, если фишка была в столбце \(i\), ее можно переместить в любой столбец \(j < i\), а фишки в самом левом столбце двигать нельзя). Фишки не должны покидать выбранную часть доски.
У Алисы и Боба есть \(q\) пар чисел \(L_i\) и \(R_i\). Для каждой такой пары они хотят определить, кто выиграет, если \(l = L_i\) и \(r = R_i\). Обратите внимание, что эти игры рассматриваются независимо (они не влияют на положение на доске в последующих играх), и оба игрока играют оптимально.
Выходные данные
Выведите строку из \(q\) символов. \(i\)-й символ должен быть A, если Алиса выигрывает при \(l = L_i\) и \(r = R_i\), или B, если выигрывает Боб.