آقای دنباله‌نژاد که کل عمرش را صرف تحلیل دنباله‌ها کرده، باور دارد می‌توان با استفاده از دنباله‌ها وقوع حوادث ناگوار را پیشبینی کرد. برای این کار آقای دنباله‌نژاد هر جفت از اعداد دنباله را تحلیل می کند و سپس میزان نحسی دنباله را محاسبه می‌کند.

آقای دنباله‌نژاد از نابجایی و همچنین از عدد $k$ متنفر است. به همین دلیل به زوج $i$‌ و $j$ که $i<j$ یک جفت شوم می‌گوید اگر $a_i > a_j$ برقرار باشد. به آن بدشگون می‌گوید اگر $a_i \oplus a_j > k$ باشد. (نماد $\oplus$ نشان‌دهندهٔ ‌xor است). جفت‌های شوم یا بدشگون می‌توانند نحسی به همراه بیاورند اما اگر یک جفت همزمان هم شوم و هم بدشگون باشد، این دو نحسی یکدیگر را خنثی می‌کنند . بدین ترتیب یک جفت نحس است اگر و تنها اگر دقیقا یکی از دو شرط شومی یا بدشگونی را داشته باشد.

آقای دنباله‌نژاد نحسی دنباله را برابر تعداد جفت‌های نحس تعریف می‌کند و برای پیشگویی نیاز به دانستن نحسی دنباله دارد. اما آقای دنباله‌نژاد که دیگر پیر و فرتوت شده است نمی‌تواند به راحتی نحسی دنباله را محاسبه کند و به همین سبب از شما خواسته تا به او در پیشبینی کردن اتفاقات بد کمک کنید.

سطر اول ورودی شامل دو عدد طبیعی $n, k$ است که $n$ همان طول دنباله است . در سطر بعدی $n$ عدد می‌آید که عدد $i$م نشان دهندهٔ $a_i$ است.

در تنها سطر خروجی میزان نحسی دنباله را خروجی دهید.

• زیرمسئله اول (۳ نمره): $1 \leq n \leq 7000$.
• زیرمسئله دوم (۱۳ نمره): $0 \leq a_i, k < 64$.
• زیرمسئله سوم (۴۰ نمره): $1 \leq n \leq 5 \times 10^4$.
• زیرمسئله چهارم (۴۴ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 10^6$
• $0 \leq k < 2^{30}$
• $0 \leq a_i < 2^{30}$

4 4
5 3 4 1

4

9 5
1 2 3 4 5 6 7 8 9

20

• سوال قبل
• سوال بعد