JOI 君 ชอบสะสมรูปภาพมากและมีรูปอยู่เป็นจำนวนมาก เมื่อไม่นานมานี้ เขาพบว่าฮาร์ดดิสก์ใกล้เต็มเพราะสะสมรูปมากเกินไป เขาไม่มีเงินซื้อฮาร์ดดิสก์ใหม่ แต่การลบรูปที่มีอยู่เป็นเรื่องทรมานอย่างยิ่งสำหรับเขา จึงตัดสินใจบีบอัดรูปอย่างเหมาะสมเพื่อลดพื้นที่จัดเก็บ

รูปภาพแทนด้วยพิกเซลทั้งหมด $2^N\times2^N$ พิกเซล เรียงเป็นสี่เหลี่ยมจัตุรัส $2^N$ แถวและ $2^N$ คอลัมน์ แต่ละพิกเซลเป็นสีขาวหรือสีดำ

JOI 君 ตัดสินใจบีบอัดรูปภาพด้วยวิธีต่อไปนี้

• หากพิกเซลทั้งหมดในรูปมีสีเดียวกัน ให้บันทึกเพียงสีนั้น ขนาดข้อมูลหลังบีบอัดในกรณีนี้คือ $1$
• มิฉะนั้น ให้แบ่งรูปเป็นรูปเล็กลง 4 รูป หากรูปมีขนาด $2^k$ แถวและ $2^k$ คอลัมน์ ให้แบ่งที่กึ่งกลางทั้งแนวตั้งและแนวนอน จะได้รูปขนาด $2^{k-1}$ แถวและ $2^{k-1}$ คอลัมน์ 4 รูป แล้วบีบอัดรูปเล็กเหล่านี้ด้วยวิธีเดียวกัน ขนาดข้อมูลหลังบีบอัดเท่ากับผลรวมของขนาดข้อมูลหลังบีบอัดของรูปเล็กทั้ง 4 รูป บวกอีก $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\le2^N$ และถ้า $T_i=1$ ให้เปลี่ยนพิกเซล $(a,X_i)$ ทุกตัวที่ $1\le a\le2^N$ จากขาวเป็นดำหรือจากดำเป็นขาว
• สำหรับแต่ละ $i$ ตรวจสอบขนาดข้อมูลหลังบีบอัดรูปที่ได้หลังจบการดำเนินการครั้งที่ $i$ ด้วยวิธีของ JOI 君

เพื่อให้ทดลองได้มากครั้งที่สุด จำเป็นต้องหาขนาดข้อมูลหลังบีบอัดอย่างรวดเร็ว

งานที่ต้องทำ

จงเขียนโปรแกรมรับจำนวนเต็ม $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\le1$ และ $1\le X_i\le2^N$ การดำเนินการครั้งที่ $i$ จะกลับสีทุกพิกเซลในแถวที่ $X_i$ จากด้านบนหาก $T_i=0$ หรือในคอลัมน์ที่ $X_i$ จากด้านซ้ายหาก $T_i=1$

ข้อมูลส่งออก

เขียน $Q$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน บรรทัดที่ $i$ ($1\le i\le Q$) ให้เขียนจำนวนเต็มหนึ่งจำนวน ซึ่งเป็นขนาดข้อมูลหลังบีบอัดรูปที่ได้หลังจบการดำเนินการครั้งที่ $i$ ด้วยวิธีของ JOI 君

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $1\le N\le20$
• $1\le Q\le2\,000\,000$

งานย่อย

งานย่อย 1 [10 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N\le6$
• $Q\le128$

งานย่อย 2 [20 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N\le10$
• $Q\le2\,048$

งานย่อย 3 [70 คะแนน]

• ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

2 3
0 1
1 2
0 3

ข้อมูลส่งออก 1

13
17
21

หมายเหตุ

ในตัวอย่างนี้ การดำเนินการ $Q=3$ ครั้งเป็นไปตามภาพต่อไปนี้

สถานะเริ่มต้น