JOI אוהב מאוד לאסוף תמונות רבות, ויש ברשותו תמונות רבות. לאחרונה הוא שם לב שבגלל שאסף יותר מדי תמונות, המקום בדיסק הקשיח עומד להיגמר. אין לו כסף לקנות דיסק קשיח חדש, אבל מחיקת תמונות שברשותו תהיה עבורו כואבת ביותר, ולכן החליט לדחוס אותן היטב כדי לצמצם את נפחן.

תמונה מיוצגת על ידי $2^N \times 2^N$ פיקסלים המסודרים בריבוע של $2^N$ שורות ו-$2^N$ עמודות. כל פיקסל הוא לבן או שחור.

JOI החליט לדחוס תמונות כאלה בשיטה הבאה.

• אם כל הפיקסלים בתמונה הם באותו צבע, שומרים רק את הצבע הזה. במקרה זה גודל הנתונים לאחר הדחיסה הוא $1$.
• אחרת, מחלקים את התמונה לארבע תמונות קטנות יותר. אם בתמונה יש $2^k$ שורות ו-$2^k$ עמודות, חוצים אותה באמצע גם אנכית וגם אופקית, ומקבלים ארבע תמונות של $2^{k-1}$ שורות ו-$2^{k-1}$ עמודות. דוחסים את ארבע התמונות הקטנות באותה שיטה. במקרה זה גודל הנתונים לאחר הדחיסה הוא סכום גדלי הנתונים הדחוסים של ארבע התמונות הקטנות, בתוספת $1$.

JOI אינו בטוח שהשיטה באמת תדחוס את התמונות, ולכן החליט לערוך ניסויים על תמונות שונות. הניסוי מתבצע כך.

• תחילה מכינים תמונה שכל הפיקסלים בה לבנים.
• עבור $i=1,\ldots,Q$, מבצעים את הפעולה: ״אם $T_i=0$, הופכים את הצבע של כל $2^N$ הפיקסלים בשורה ה-$X_i$ מלמעלה; אם $T_i=1$, הופכים את הצבע של כל $2^N$ הפיקסלים בעמודה ה-$X_i$ משמאל״. כלומר, אם מסמנים ב-$(a,b)$ את התא בשורה ה-$a$ מלמעלה ובעמודה ה-$b$ משמאל, אז לכל $i$, אם $T_i=0$ משנים את הפיקסלים $(X_i,b)$ עבור $1 \le b \le 2^N$, ואם $T_i=1$ משנים את הפיקסלים $(a,X_i)$ עבור $1 \le a \le 2^N$: לבן הופך לשחור ושחור הופך ללבן.
• עבור כל $i$, בודקים את גודל הנתונים לאחר דחיסת התמונה בשיטה של JOI, לאחר סיום הפעולה ה-$i$.

כדי לבצע בניסוי כמה שיותר פעולות, צריך לחשב במהירות את גודל הנתונים הדחוסים.

המשימה

בהינתן מספר שלם $N$ המציין את גודל התמונה, מספר הפעולות $Q$ וההוראות של $Q$ הפעולות, כתבו תוכנית שמחשבת לאחר כל פעולה את גודל הנתונים לאחר דחיסת התמונה בשיטה של JOI.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה שני מספרים שלמים $N,Q$ המופרדים ברווח, המציינים שגודל התמונה הוא $2^N$ שורות ו-$2^N$ עמודות ושמספר הפעולות הוא $Q$.
• $Q$ השורות הבאות מכילות הוראות לפעולות. השורה ה-$i$ ($1 \le i \le Q$) מכילה שני מספרים שלמים $T_i,X_i$ ($0 \le T_i \le 1$ וגם $1 \le X_i \le 2^N$) המופרדים ברווח. הפעולה ה-$i$ הופכת את צבעי כל הפיקסלים בשורה ה-$X_i$ מלמעלה אם $T_i=0$, או בעמודה ה-$X_i$ משמאל אם $T_i=1$.

פלט

כתבו $Q$ שורות לפלט הסטנדרטי. בשורה ה-$i$ ($1 \le i \le Q$) כתבו מספר שלם אחד המציין את גודל הנתונים לאחר דחיסת התמונה בשיטה של JOI, לאחר סיום הפעולה ה-$i$.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $1 \le N \le 20$.
• $1 \le Q \le 2\,000\,000$.

תת־משימות

תת־משימה 1 [10 נקודות]

מתקיימים התנאים הבאים.

• $N \le 6$.
• $Q \le 128$.

תת־משימה 2 [20 נקודות]

מתקיימים התנאים הבאים.

• $N \le 10$.
• $Q \le 2\,048$.

תת־משימה 3 [70 נקודות]

• אין מגבלות נוספות.

דוגמאות

קלט 1

2 3
0 1
1 2
0 3

פלט 1

13
17
21

הסבר

בדוגמה זו, $Q=3$ הפעולות מתבצעות באופן הבא.

初期状態: המצב ההתחלתי