La cena de Nochevieja avanza como siempre: comida, villancicos y el inevitable cuñado que asegura saber de todo.
Este año, Diego se proclama mago oficial de la familia y nos reta con un supuesto truco imposible.
Promete que, si logramos descubrir el valor de una moneda oculta usando únicamente lógica, nos dará 10€.
El reto comienza con dos cantidades conocidas:
- \(n_1\) monedas que inicialmente muestran cara (C)
- \(n_2\) monedas que inicialmente muestran cruz (X)
En total hay \(n = n_1 + n_2\) monedas sobre la mesa.
Se cumple que \(n_1 + n_2 \ge 2\) y \(0 \le n_1, n_2 \le 2 \cdot 10^5\).
Diego realizará exactamente \(m\) movimientos, donde \(0 \le m \le 10^{18}\).
En cada movimiento elige una moneda y la voltea: si muestra cara pasa a cruz, si muestra cruz pasa a cara.
Puede repetir monedas, alternarlas o intentar despistarnos… pero deberá realizar exactamente \(m\) volteos.
Al finalizar, ocultará exactamente una moneda.
Nosotros podremos ver las otras \(n − 1\) monedas.
Debemos deducir si dicha moneda es cara o cruz y si lo conseguimos, Diego tendrá que pagar.
Entrada
La primera línea contiene un entero \(t\), el número de partidas.
Se garantiza que \(1 \le t \le 10^4\).
Para cada partida:
- Una línea con tres enteros: \(n_1\), \(n_2\) y \(m\), respectivamente.
- Una línea con \(n_1 + n_2\) caracteres que representan el estado final de las monedas (C → cara, X → cruz, - → moneda oculta).