AlgoLiga 2018

Jak powszechnie wiadomo, Bajtlandia rywalizuje z Bajtocją o miano najbardziej rozrywkowego królestwa. Ostatnio w Bajtocji odbył się festyn muzyczny. W związku z tym, król Bajtlandii postanowił nie być gorszy i również zorganizował festyn, jednak taki z grami i konkursami. Jedną z takich gier są Wieże bogactwa. W każdej partii bierze udział dokładnie dwóch graczy. Mają oni do dyspozycji n stosów bajtalarów o [niekoniecznie] różnej wysokości. Gra polega na tym, że kolejno zdejmują z dowolnej wieży dowolną ilość bajtalarów. Ten kto usunie ostatniego bajtalara wygrywa. Wszyscy mieszkańcy Bajtlandii grają optymalnie, a związku z czym postanowiono utrudnić im zadanie. W dowolnej chwili nadzorca konkursu może dołożyć wieżę o wysokości x bajtalarów do każdej wieży od indeksu i do j. Owe dołożone wieże nie są jednak umieszczane na poprzednich, lecz za nimi. W trakcie rozgrywki wygląda to zatem tak, że jest n rzędów wież o niekoniecznie takiej samej długości, a same wieże w rzędzie również mogą być różnej wysokości. Co więcej, nadzorca może wybrać dowolny spójny ciąg rzędów wież, na którym mają grać zawodnicy. A więc na początku grają na wieżach od indeksu 1 do n, ale później indeksy te mogą się zmienić na np. 7 i 9. Nie chcąc faworyzować któregoś z graczy, nadzorca chciałby wiedzieć po każdej zmianie przedziału wież, na których grają zawodnicy, kto wygra (zakładając, że dany ruch należy do gracza A). Wyeliminuje to sytuację, że modyfikacje nadzorcy będą ciągle umożliwiały zwycięstwo wyłącznie jednemu z graczy.

Wejście

W pierwszej linii znajdują się liczby n i q (0 < n,q ≤ 10⁶) - ilość wież oraz zapytań. Druga linia zawiera n liczb z przedziału 1..10⁹. W następnych q liniach znajdują się zapytania. Zapytanie rozpoczyna się od liczby całkowitej b (0 ≤ b ≤ 1). Jeśli b=0 to linię kończą trzy liczby: a b x (0 < a,b ≤ n, 0 < x ≤ 10⁹) oznaczające, że nadzorca dodał wieżę składającą się z x bajtalarów do rzędów od indeksu a do b. Dla b=1 są tylko dwie liczby a b (0 < a, b ≤ n) i oznaczają, że gracze mogą operować jedynie na rzędach wież od indeksu a do b.

Wyjście

Dla każdego testu z b=1 należy wypisać A, jeśli wygra zawodnik rozpoczynający lub B w przeciwnym wypadku.

Przykład

Wejście:
5 3
5 7 2 1 4
1 2 4
0 1 3 3
1 3 4

Wyjście:
A
B

Wyjaśnienie do przykładu

W pierwszym zapytaniu interesuje nas przedział od 2 do 4 wieży. Gracz A może wygrać biorąc np. 4 monety ze szczytu wieży z indeksu 2 (pozostają wieże o wysokościach: 3, 2, 1). Jeśli gracz B zlikwiduje wieżę o wysokości 1, to gracz A weźmie monetę z wieży o wysokości 3 i pozostaną dwie wieże o wysokości 2. Gracz B będzie musiał wtedy wziąć jedną monetę, gracz A również weźmie 1 monetę, potem znów gracz B i na końcu gracz A - wygrywając. Jeśli gracz B przy sytuacji 3, 2, 1 weźmie jednak monetę z środkowej wieży, to gracz A zlikwiduje pierwszą wieżę i zostaną dwie wieże z 1 monetą - gracz A znów wygra. Jeśli przy 3, 2, 1 gracz B zlikwiduje całą środkową wieżę, to gracz A znów sprawi by pozostały dwie wieże z 1 bajtalarem i wygra. Cokolwiek gracz B by nie zrobił, gracz A może wygrać jeśli wykona odpowiednie ruchy.

Następnie dodajemy wieże z 3 monetami do indeksów 1, 2 i 3. Sytuacja z góry będzie wyglądać następująco (liczby oznaczają wysokość wieży):

Na końcu mamy zapytanie o indeksy 3 oraz 4. Mamy więc do dyspozycji wieże o wysokości: 2, 3 i 1. Jak już wiemy z poprzedniego scenariusza, gracz zaczynający przy takim rozdaniu nie ma szans na wygraną. Wtedy był to gracz B, jednak teraz jest to gracz A. Gracz B tym razem wygrywa.