+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- آقای دنباله‌نژاد که کل عمرش را صرف تحلیل دنباله‌ها کرده، باور دارد می‌توان با استفاده از دنباله‌ها وقوع حوادث ناگوار را پیشبینی کرد. برای این کار آقای دنباله‌نژاد هر جفت از اعداد دنباله را تحلیل می‌کند و سپس میزان نحسی دنباله را محاسبه می‌کند. آقای دنباله‌نژاد از نابجایی و همچنین از عدد $k$ متنفر است. به همین دلیل به زوج $i$‌ و $j$ که $i<j$ یک جفت *شوم* می‌گوید اگر $a_i > a_j$ برقرار باشد. به آن *بدشگون* می‌گوید اگر $a_i \oplus a_j > k$ باشد (نماد $\oplus$ نشان‌دهندهٔ ‌`xor` است). جفت‌های شوم یا بدشگون می‌توانند نحسی به همراه بیاورند اما اگر یک جفت همزمان هم شوم و هم بدشگون باشد، این دو نحسی یکدیگر را خنثی می‌کنند. بدین ترتیب یک جفت نحس است اگر و تنها اگر دقیقا یکی از دو شرط شومی یا بدشگونی را داشته باشد. آقای ~دنباله‌نژاد نحسی دنباله را برابر تعداد جفت‌های نحس تعریف می‌کند و برای پیشگویی نیاز به دانستن نحسی دنباله دارد.~ اما آقای دنباله‌نژاد که دیگر پیر و فرتوت شده است نمی‌تواند به راحتی نحسی دنباله را محاسبه کند و به همین سبب از شما خواسته تا به او در پیشبینی کردن اتفاقات بد کمک کنید. # ورودی سطر اول ورودی، شامل دو عدد طبیعی $n$ طول دنباله و $k$ است. $$1 \leq n \leq 10^6, \quad 0 \leq k < 2 ^ {30}$$ در سطر بعدی، $n$ عدد می‌آید که عدد $i$م نشان دهندۀ $a_i$ است. $$1 \leq a_i < 2^{30}$$ # خروجی در تنها سطر خروجی میزان نحسی دنباله را خروجی دهید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۳ | $$1 \leq n \leq 7000$$ | | ۲ | ۱۳ | $0 \leq a_i,k < 64$ | | ۳ | ۴۰ | $$1 \leq n \leq 5\times 10^4$$ | | ۴ | ۴۴ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 4 4 5 3 4 1 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 9 5 1 2 3 4 5 6 7 8 9 ``` ## خروجی نمونه ۲ ``` 20 ```

حل سؤال در بانک سؤالات