یکدستی جدول

جعفر و اصغر از شاگردان آقا داوود هستند که برای مسابقات کشوری آماده می‌شوند. آقا داوود با توجه به نتایج تمرینات آن‌ها به این نتیجه رسیده است که جعفر در کارهای فکری و اصغر در کارهای قدرتی ضعیف هستند. حال او یک تمرین ویژه برای آن‌ها طراحی کرده، که هر دوی آن‌ها بتوانند از آن استفاده کنند. تمرین آنها به این صورت است: یک جدول $2^N×2^N$ که در ابتدا تمام خانه‌های آن خالی است، داریم. حال در هر مرحله آقا داوود به اصغر یک سطر یا یک ستون را نشان می‌دهد، سپس اصغر روی آن سطر و یا ستون حرکت کرده و بر روی تمامی خانه‌هایی که راه می‌رود یک وزنه‌ی یک کیلوگرمی می‌گذارد. حال بعد از به پایان رسیدن کار اصغر، نوبت به جعفر می‌رسد. وظیفه‌ی او این است که بعد از هر بار به پایان رسیدن کار اصغر یکدستی جدول را اعلام کند. یکدستی جدول $M$ با ابعاد $2^N×2^N$، به این صورت محاسبه می‌شود:

• اگر زوجیت تمامی خانه‌های $M$، از لحاظ مجموع وزنه‌هایی که روی آن قرار دارد یکسان بودند، یکدستی این جدول 1 است.
• در صورتی که شرط بالایی برقرار نبود، $M$ را به چهار زیر جدول به ابعاد $2^{N-1}×2^{N-1}$ افراز می‌کنیم (دقت کنید که چنین تقسیم‌بندی یکتا است). حال یکدستی $M$ مساوی است با مجموع یکدستی این چهار زیر جدول به علاوه یک.

حال چون در المپیاد کامپیوتر به کارهای قدرتی در حد استانداردهای آقا داوود نیاز نیست، از شما می‌خواهیم که با گرفتن دستورهای آقا داوود، در نقش جعفر عمل کنید و پاسخ‌های او را در خروجی چاپ کنید. نقش اصغر را هم ما بر عهده می‌گیریم.(!)

• در سطر اول ورودی دو عدد طبیعی، $1 \leq N \leq 20$ و $1\leq Q \leq 2* 10^6$ تعداد دستورهای آقا داوود آمده است.
• سطرهای دوم تا $Q+1$-ام هر کدام شامل یک دستور آقا داوود است. هر کدام از این سطرها شامل یک عدد، $T \in \{0, 1\}$ و یک عدد طبیعی $1 \leq X \leq 2^N$ است. در صورتی که $T=0$ باشد، آقا داوود یک سطر را نشان داده و اگر $T=1$ باشد، یک ستون را نشان داده است. عدد $X$ نیز بیانگر شماره سطر یا ستون مورد نظر است. سطرها از بالا به پایین و ستون‌ها از چپ به راست با اعداد 1 تا $2^N$ شماره‌گذاری شده‌اند. در هرخط $T$ و $X$ دقیقاً با یک فاصله از هم جدا شده‌اند.
• در ۱۰ درصد از ورودی‌ها، $1 \leq N \leq 6$ و $1 \leq Q \leq 128$ است.
• در ۳۰ درصد از ورودی‌ها، $1 \leq N \leq 10$ و $1 \leq Q \leq 2048$ است.

خروجی شامل $Q$ سطر است که عدد سطر $i$-ام یکدستی جدول بعد از دستور $i$-ام را نشان می‌دهد.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال قبل