CF2246E lce4113 and Security Game

This is an interactive problem. Additionally, hacks are disabled for this problem. There are two hidden integers $ b $ and $ v $ such that $ b \in \{0,1\} $ and $ 0 \le v \lt 2^{30}. $ There is also a hidden operation $ \mathrm{ty}, $ which is either $ \& $ or $ |. $ Here, $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Additionally, $ | $ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). Your goal is to guess $ b. $ The interaction proceeds as follows: - First, you send a value $ x $ to the interactor, such that $ 0 \le x \lt 2^{30} $ . - The interactor sends back $ v\,\mathrm{ty}\,x $ . Formally, it will send back $ o(v,x) $ , where $$$ o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases} $$$ - You then send two numbers $ m_0 $ and $ m_1 $ , where $ 0 \le m_0, m_1 \lt 2^{30}. $ - Finally, the interactor will send back $ m_b \oplus v, $ where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). After the interaction, you have to output $ b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows. Note that this is the only initial input given.

N/A

The example interaction proceeds as follows: SolutionInteractorExplanation $ 3 $ There are $ 3 $ test cases. $ 2 $ The solution chooses $ x = 2 $ . $ 0 $ The interactor sends back $ x\,\mathrm{ty}\,v = 2\,\&\,1 = 0. $ $ 314 $ $ 159 $ The solution sends $ m_0 = 314 $ and $ m_1 = 159. $ $ 315 $ The interactor responds with $ m_b \oplus v = m_0 \oplus v = 315. $ $ 0 $ The solution determines $ b = 0. $ $ 3 $ The next test case begins. The solution chooses $ x = 3 $ . $ 3 $ The interactor sends back $ x\,\mathrm{ty}\,v = 3\,|\,1 = 3. $ $ 12 $ $ 34 $ The solution sends $ m_0 = 12 $ and $ m_1 = 34. $ $ 35 $ The interactor responds with $ m_b \oplus v = m_1 \oplus v = 35. $ $ 1 $ The solution determines $ b = 1. $ $ 0 $ The final test case begins. The solution chooses $ x = 0 $ . $ 5 $ The interactor sends back $ x\,\mathrm{ty}\,v = 0\,|\,5 = 5. $ $ 0 $ $ 0 $ The solution sends $ m_0 = 0 $ and $ m_1 = 0. $ $ 5 $ The interactor responds with $ m_b \oplus v = m_1 \oplus v = 5. $ $ 1 $ The solution determines $ b = 1. $ Note that the queries made by the example solution may not yield enough information to determine the hidden bit $ b. $ Additionally the empty lines in the example interaction are given for readability and need not be outputted in the solution. The hidden values in the test cases are given below. Test # $ v $ $ b $ $ \mathrm{ty} $ $ 1 $ $ 1 $ $ 0 $ $ \& $ $ 2 $ $ 1 $ $ 1 $ $ | $ $ 3 $ $ 5 $ $ 1 $ $ | $