Ұзындығы \(n\) болатын \(a_1, a_2, \ldots, a_n\) тізбегі берілген.

Тізбектегі \((i, j)\) жұбы инверсия деп аталады, егер \(i < j\) және \(a_i > a_j\) болса.

Сізге \(q\) сұрауға жауап беру қажет. Әр сұрауда бүтін сан \(x\) беріледі. Әрбір \(x\) үшін \((a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x)\) массивтегі инверсияларының жалпы санын есептеу қажет, мұндағы \(\oplus\) биттік XOR операциясын білдіреді.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(q\) (\(1 \le n,\ q \le 10^6\)) берілген.

Екінші жолда \(n\) бүтін сан \(a_1,\ a_2,\ \dots,\ a_n\) (\(0 \le a_i \le 10^9\)) — сандар тізбегі берілген.

Содан кейін \(q\) жолдар келеді, әрқайсысы бір бүтін сан \(x\) (\(0 \le x \le 10^9\)) — сұрау мәндері.

Шығару

Әр сұраудан кейін массивтегі \((a_1 \oplus x,\ a_2 \oplus x,\ \dots,\ a_n \oplus x)\) инверсияларының санын шығарыңыз.

Мысалдар

Енгізу 1

5 5
1 2 3 4 5
1
2
3
4
5

Жауап 1

2
2
4
6
8