Tommy and Alan decide to celebrate -day by doing some calculus problems with their friends!
There are problems, and the -th problem gives points. The -th person has a difficulty adjustment of , which means that the -th problem has an adjusted difficulty of . Additionally, the -th person can only solve problems which have an adjusted difficulty of at most . That is, the -th person can solve the -th problem if .
For each of the people, can you figure out, over all the problems they can solve, which will give them the most points?
stands for the bitwise XOR operator (e.g. ).
The first line contains two space-separated integers and .
The second line contains space-separated integers .
The next lines each contain the description of one of Tommy and Alan's friends. Each query contains two space-separated integers and .
The following table shows how the available 15 marks are distributed.
|Mark Awarded||Number of Problems||Number of Queries||Additional Constraints|
For each person, output the number of points of the hardest problem they can solve. It can be proven that at least one problem is always possible.
Sample Input 1
5 2 1 2 3 4 5 1 3 2 4
Output for Sample Input 1
Explanation of Output for Sample Input 1
Person can do problems , , , and . Of those, problem gives the most points, .
Person can also gain points by doing problem .
Sample Input 2
8 2 9 3 5 6 6 2 4 3 2 5 6 1
Output for Sample Input 2
Explanation of Output for Sample Input 2
Person can do problems , , , , and . Problem gives points, which is the highest.
Person can score points by doing problem .