CF2203D Divisibility Game

Alice and Bob are playing a game. They have an array $ a $ of $ n $ elements and an array $ b $ of $ m $ elements. The players take turns. Alice goes first. On their turn, each player chooses a number $ x $ from array $ a $ and a number $ y $ from array $ b $ . Alice has her own rule for choosing $ x $ and $ y $ , and Bob has his: - Alice must choose $ x $ and $ y $ such that $ y $ is divisible by $ x $ . - Bob must choose $ x $ and $ y $ such that $ y $ is not divisible by $ x $ . After choosing $ x $ and $ y $ , $ y $ is removed from the array $ b $ (but $ x $ remains in $ a $ ). When $ y $ is removed from $ b $ , if there are multiple occurrences of $ y $ , only one is removed. The player who cannot make a move loses. Who will win if both players play optimally?

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^{6} $ ). The second line of each test case contains $ n $ integers $ a_{i} $ ( $ 1 \le a_{i} \le n + m $ ) — the elements of the array $ a $ . The last line of each test case contains $ m $ integers $ b_{i} $ ( $ 1 \le b_{i} \le n + m $ ) — the elements of the array $ b $ . Additional constraints on the input: - the sum of $ n $ over all test cases does not exceed $ 10^6 $ ; - the sum of $ m $ over all test cases does not exceed $ 10^6 $ .

For each test case, print one word: - Alice if Alice wins; - Bob if Bob wins.

Consider the first test case. Let's show how Alice wins through the moves: - Alice's move: $ x = 3, y = 6 $ (after this, $ 6 $ will be removed from $ b $ , resulting in $ b = [7, 12] $ ) - Bob's move: $ x = 3, y = 7 $ (Bob will choose $ y = 7 $ on his turn anyway, since there is no $ x $ that does not divide $ y = 12 $ , after this move $ b = [12] $ ) - Alice's move: $ x = 4, y = 12 $ (after this move, $ b $ becomes empty) - Bob's move: Bob loses, as he cannot make a move