====== SEQUENCE ======


دنباله‌ی اعداد $a_1,a_2,\cdots,a_n$ را در نظر بگیرید. این دنباله $q$ بار تغییر می‌کند. هر تغییر را می‌توان به صورت $(p,x)$ نمایش داد به این معنا که عضو $p$ ام دنباله بعد از تغییر برابر با $x$ می‌شود. حال شما باید برنامه‌ای بنویسید که بعد از هر تغییر کمترین عدد صحیح و نامنفی $t$ را پیدا کند به طوری‌که دنباله‌ی 
$a_1 \oplus t, a_2 \oplus t, \cdots, a_n \oplus t$
 دارای کمترین تعداد نابه‌جایی باشد. برنامه‌ی شما باید این مقدار $t$ و تعداد نابجایی‌ها، در دنباله‌ی تولید شده توسط آن را، در خروجی چاپ کند.


**علامت $\oplus$ نشان‌دهنده‌ی عملگر $\mathrm{xor}$است. در یک دنباله‌ی دلخواه از اعداد مانند $c_1,c_2,\cdots,c_n$ جفت $(i,j)$ یک نابجایی است اگر و فقط اگر $i<j$ و $c_i > c_j$ باشد.**


===== ورودی =====

در سطر اول ورودی دو عدد طبیعی $n$، طول دنباله‌ی ورودی، و $q$، تعداد تغییر‌های دنباله، آمده است.

سطر دوم شامل $n$ عدد صحیح $a_1,a_2,\cdots,a_n$ است.

در هر یک از $q$ سطر بعدی به ترتیب دو عدد صحیح $p$ و $x$ آمده است که به معنای تغییر عضو $p$ ام دنباله به $x$ است.


===== خروجی =====


خروجی شامل $q$ سطر است که در $i$ امین $(1\leq i\leq q)$ سطر از آن، پاسخ مسئله بعد از $i$‌ تغییر اول آمده است.

===== زیرمسئله‌ها =====


  * زیرمسئله اول (۱۳ نمره): $n,q\leq 1000$
  * زیرمسئله دوم (۱۹ نمره): $q=1$
  * زیرمسئله سوم (۴۹ نمره): $n,q\leq 10^{4}$
  * زیرمسئله چهارم (۱۹ نمره): بدون محدودیت اضافی


===== محدودیت‌ها =====

  * $1\leq n,q\leq 5\times 10^{4}$
  * $0\leq a_i, x< 2^{30}$
  * $1\leq p\leq n$

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 3 \\ 0 1 0 0 \\ 1 1 \\ 3 1 \\ 1 0|1 0 \\ 1 0 \\ 0 2|
|8 1 \\ 9 1 8 3 4 7 9 3 \\ 3 0|9 7|
</WRAP>
===== شرح ورودی و خروجی نمونه =====

در ورودی نمونه‌ی اول، وضعیت دنباله بعد از هر تغییر به صورت زیر بررسی شده است:

  * بعد از تغییر اول: در این صورت دنباله‌ی اولیه به $1,1,0,0$ تبدیل می‌شود. در این حالت در صورتی که به جای $t$، عدد $1$ قرار دهیم، به دنباله‌ی $0,0,1,1$ می‌رسیم که تعداد نابجایی‌های آن صفر است. در صورتی که $t$ برابر با $0$ باشد، دنباله تغییر نمی‌کند و دارای چهار نابجایی است، بنابراین $t=1$ بهتر است. با توجه به این‌که به ازای $t=1$ تعداد نابجایی‌ها صفر است، بنابراین به ازای $t$‌های بزرگ‌تر تعداد نابجایی‌ها کم‌تر نیست. پس پاسخ همان $t=1$ است.
  * یعد از تغییر دوم: در این صورت به دنباله‌ی $1,1,1,0$ می‌رسیم. در این حالت در صورتی که به جای $t$، عدد $1$ قرار دهیم، به دنباله‌ی $0,0,0,1$می‌رسیم که تعداد نابجایی‌های ان صفر است. در صورتی که $t=0$ باشد، دنباله تغییر نمی‌کند و بنابراین تعداد نابجایی‌های آن برابر با $3$ است. با استدلالی مشابه حالت قبلی، $t=1$ پاسخ مورد نظر است.
  * بعد از تغییر سوم: در این صورت به دنباله‌ی  $0,1,1,0$ می‌رسیم. در صورتی که $t=0$ باشد، تعداد نابجایی‌ها برابر با $2$ است و  در صورتی که $t=1$ باشد نیز تعداد نابجایی‌ها برابر با $2$ است. می‌توان ثابت کرد که به ازای $t$‌های بزرگ‌تر از $1$ نیز تعداد نابجایی‌ها کم‌تر از $2$‌ نمی‌شود. با توجه به این‌که کوچک‌ترین $t$ در بین‌ آن‌هایی که نابجایی را کمینه می‌کنند باید به عنوان پاسخ در نظر گرفته شود، بنابراین پاسخ مسئله برابر با $0$‌ است.

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]