1395C.md (1508B)
1 Source: https://codeforces.com/problemset/problem/1395/C 2 3 C. Boboniu and Bit Operations 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Boboniu likes bit operations. He wants to play a game with you. 22 23 Boboniu gives you two sequences of non-negative integers $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_m$. 24 25 For each $i$ ($1\le i\le n$), you're asked to choose a $j$ ($1\le j\le m$) and let $c_i=a_i\& b_j$, where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Note that you can pick the same $j$ for different $i$'s. 26 27 Find the minimum possible $c_1 | c_2 | \ldots | c_n$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). 28 29 Input 30 31 The first line contains two integers $n$ and $m$ ($1\le n,m\le 200$). 32 33 The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i \lt 2^9$). 34 35 The next line contains $m$ integers $b_1,b_2,\ldots,b_m$ ($0\le b_i \lt 2^9$). 36 37 Output 38 39 Print one integer: the minimum possible $c_1 | c_2 | \ldots | c_n$. 40 41 Examples 42 43 Input 44 45 ``` 46 4 2 47 2 6 4 0 48 2 4 49 ``` 50 51 Output 52 53 ``` 54 2 55 ``` 56 57 Input 58 59 ``` 60 7 6 61 1 9 1 9 8 1 0 62 1 1 4 5 1 4 63 ``` 64 65 Output 66 67 ``` 68 0 69 ``` 70 71 Input 72 73 ``` 74 8 5 75 179 261 432 162 82 43 10 38 76 379 357 202 184 197 77 ``` 78 79 Output 80 81 ``` 82 147 83 ``` 84 85 Note 86 87 For the first example, we have $c_1=a_1\& b_2=0$, $c_2=a_2\& b_1=2$, $c_3=a_3\& b_1=0$, $c_4 = a_4\& b_1=0$.Thus $c_1 | c_2 | c_3 |c_4 =2$, and this is the minimal answer we can get.