Batalha de Rotações de Chaves Criptográficas
Ada e Py disputam um torneio de segurança digital com uma regra diferente. Cada uma possui uma senha (string de letras minúsculas). Antes de cada rodada, cada jogadora pode rotacionar ciclicamente sua senha quantas posições quiser. O sistema declara vencedora quem enviar a rotação lexicograficamente menor. Se iguais, empate. Ambas jogam de forma ótima.
Uma rotação de uma string $s$ de comprimento $n$ consiste em escolher um índice $0 \le k < n$ e formar $s[k], s[k{+}1], \ldots, s[n{-}1], s[0], \ldots, s[k{-}1]$. Por exemplo, as rotações de "bca" são "bca", "cab" e "abc", sendo a menor "abc".
Atenção: rotacionar é diferente de permutar livremente. A string "cb" tem rotações "cb" e "bc", portanto sua melhor rotação é "bc", enquanto a permutação mínima seria também "bc". Já "cbad" tem rotações "cbad", "badc", "adcb", "dcba", sendo a mínima "adcb", enquanto a permutação mínima seria "abcd". São diferentes!
O torneio tem $Q$ eventos de três tipos:
1 s: Ada concatena a string $s$ ao final da sua senha.2 s: Py concatena a string $s$ ao final da sua senha.3: rodada em que cada jogadora envia sua rotação lexicograficamente mínima e o sistema decide a vencedora.
Uma string $A$ é lexicograficamente menor que $B$ se, na primeira posição em que diferem, a letra de $A$ antecede a de $B$, ou se $A$ é prefixo próprio de $B$.
Para cada evento do tipo 3, imprima ADA, PY ou EMPATE.
Input
A primeira linha contém a senha inicial de Ada $s_A$.
A segunda linha contém a senha inicial de Py $s_P$.
A terceira linha contém $Q$ $(1 \le Q \le 10^5)$.
As próximas $Q$ linhas descrevem os eventos. Para tipo 1 ou 2: t s. O somatório dos comprimentos de todas as strings da entrada (incluindo $s_A$ e $s_P$ iniciais e todas as strings $s$ das operações) não excede $2 \times 10^3$.
Output
Para cada evento do tipo 3, imprima ADA, PY ou EMPATE.
cb bc 5 3 1 a 3 2 a 3
EMPATE ADA PY
Explanation 1:
Rodada 1: $s_A = \text{"cb"}$, rotações: $\text{"cb"}, \text{"bc"}$ → mínima $\text{"bc"}$. $s_P = \text{"bc"}$, rotações: $\text{"bc"}, \text{"cb"}$ → mínima $\text{"bc"}$. Iguais → EMPATE.
Rodada 2: $s_A = \text{"cba"}$, rotações: $\text{"cba"}, \text{"bac"}, \text{"acb"}$ → mínima $\text{"acb"}$. $s_P = \text{"bc"}$ → mínima $\text{"bc"}$. Comparando $\text{"acb"}$ vs $\text{"bc"}$: $'a' < 'b'$ → ADA.
Rodada 3: $s_A = \text{"cba"}$ → mínima $\text{"acb"}$. $s_P = \text{"bca"}$, rotações: $\text{"bca"}, \text{"cab"}, \text{"abc"}$ → mínima $\text{"abc"}$. Comparando $\text{"acb"}$ vs $\text{"abc"}$: $'a'='a'$, $'c' > 'b'$ → PY.
cbad abcd 1 3
PY
a b 3 1 b 2 a 3
EMPATE