problem.txt (1859B)
1 F1. XOR Transformations (Easy Version) 2 time limit per test 3 4 seconds 4 memory limit per test 5 512 megabytes 6 7 This is the easy version of the problem. The difference between the versions is that in this version, the constraints on n and q are smaller. You can make hacks only if you have solved all versions of this problem. 8 9 For an array b consisting of m integers, define a transformation as follows: 10 11 Write down the values bi⊕bj for all 1≤i<j≤m, where ⊕ denotes the bitwise XOR operation.. 12 Take the m smallest among the written values. 13 Replace the elements of the array with the taken m values. 14 15 For example, consider the transformation of the array [6,7,8,9,15]. We write down the values 1,1,6,7,8,9,14,14,15,15. After the transformation, the array becomes [1,1,6,7,8] — the 5 smallest elements. 16 17 You are given an array a consisting of n non-negative integers. Let max(a) denote the maximum element of the array a, and min(a) — the minimum. Your task is to answer q queries, each of which gives you one integer x. For each query, find the value of max(a)−min(a) after x transformations on the array. Note that the queries are independent, i.e. before each query, the array a is restored to its original state. 18 Input 19 20 Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows. 21 22 The first line of each test case contains two integers n and q (5≤n≤2000,1≤q≤2000) — the size of the array and the number of queries. 23 24 The second line of each test case contains n integers a1,a2,…,an (0≤ai<230). 25 26 The next q lines of each test case contain an integer x (0≤x<230). 27 28 It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 2000. 29 Output 30 31 For each test case, output q integers — the answer to each query.