Terdapat sebuah papan catur dengan $n$ baris dan $m$ kolom. Beberapa petak pada papan tersebut rusak. Ada dua kuda di papan, yang dikendalikan oleh Alice dan Bob. Gerakan kuda ditentukan oleh dua parameter $r$ dan $c$. Pada setiap langkah, Alice atau Bob dapat memindahkan kudanya ke petak yang berjarak $r$ petak secara horizontal dan $c$ petak secara vertikal, atau $r$ petak secara vertikal dan $c$ petak secara horizontal.
Alice dan Bob bermain bergantian, dimulai oleh Alice. Pada setiap giliran, pemain memindahkan kudanya sendiri. Namun, pemain tidak boleh memindahkan kuda ke petak yang rusak atau ditempati oleh kuda lainnya.
Ada satu batasan tambahan. Konfigurasi kedua kuda dapat dipandang sebagai pasangan terurut $(a,b)$, dengan $a$ adalah petak Alice dan $b$ adalah petak Bob. Konfigurasi yang sudah pernah terjadi tidak boleh diulangi.
Seorang pemain kalah jika tidak dapat melakukan langkah pada gilirannya. Tentukan pemenangnya jika kedua pemain bermain secara optimal.
Masukan
Baris pertama berisi empat bilangan bulat $n$, $m$, $r$, dan $c$ ($1 \le n,m \le 1000$, $0 \le r<n$, $0 \le c<m$).
Masing-masing dari $n$ baris berikutnya berisi sebuah string sepanjang $m$. Bersama-sama, baris-baris ini mendeskripsikan papan catur. Ada empat jenis petak:
- “@”: Petak tersebut rusak.
- “.”: Petak tersebut tidak rusak.
- “A”: Petak tersebut tidak rusak. Ini adalah posisi awal kuda Alice.
- “B”: Petak tersebut tidak rusak. Ini adalah posisi awal kuda Bob.
Dijamin bahwa petak “A” dan “B” masing-masing muncul tepat satu kali pada papan.
Keluaran
Keluarkan nama pemenang: “Alice” atau “Bob”.
Contoh
Masukan 1
2 3 1 2 A@. B@.
Keluaran 1
Alice
Catatan
Pada langkah pertama, Alice memindahkan kudanya ke petak $(2,3)$.
Pada langkah kedua, Bob memindahkan kudanya ke petak $(1,3)$.
Pada langkah ketiga, Alice memindahkan kudanya kembali ke petak $(1,1)$.
Pada langkah keempat, Bob tidak dapat memindahkan kudanya kembali ke petak $(2,1)$, karena ini akan membentuk pasangan terurut petak $(1,1),(2,1)$ yang sama dengan posisi awal. Alice menang.