B"Ivan loves burgers and spending money. There are n burger joints on the street where Ivan lives. Ivan has q friends, and the i -th friend suggested to meet at the joint l_i and walk to the joint r_i (l_i <= q r_i) . While strolling with the i -th friend Ivan can visit all joints x which satisfy l_i <= q x <= q r_i . For each joint Ivan knows the cost of the most expensive burger in it, it costs c_i burles. Ivan wants to visit some subset of joints on his way, in each of them he will buy the most expensive burger and spend the most money. But there is a small issue: his card broke and instead of charging him for purchases, the amount of money on it changes as follows. If Ivan had d burles before the purchase and he spent c burles at the joint, then after the purchase he would have d oplus c burles, where oplus denotes the bitwise XOR operation. Currently Ivan has 2^{2^{100}} - 1 burles and he wants to go out for a walk. Help him to determine the maximal amount of burles he can spend if he goes for a walk with the friend i . The amount of burles he spends is defined as the difference between the initial amount on his account and the final account. The first line contains one integer n ( 1 <= q n <= q 500 ,000 ) -- the number of burger shops. The next line contains n integers c_1, c_2, ldots, c_n ( 0 <= q c_i <= q 10^6 ), where c_i -- the cost of the most expensive burger in the burger joint i . The third line contains one integer q ( 1 <= q q <= q 500 ,000 ) -- the number of Ivan's friends. Each of the next q lines contain two integers l_i and r_i ( 1 <= q l_i <= q r_i <= q n ) -- pairs of numbers of burger shops between which Ivan will walk. Output q lines, i -th of which containing the maximum amount of money Ivan can spend with the friend i . In the first test, in order to s"...