คำอธิบายโจทย์
การแข่งขันจะขาดโจทย์โครงสร้างข้อมูลไปไม่ได้ แม้ว่ามันจะเป็นเพียงโจทย์แจกลูกโป่งก็ตาม
คุณได้รับเมทริกซ์ $M$ ให้สมาชิกในแถวที่ $i$ และคอลัมน์ที่ $j$ ของเมทริกซ์คือ $M_{i,j}$ และให้จำนวนแถวและจำนวนคอลัมน์เป็น $n$ และ $m$ ตามลำดับ เริ่มต้น $n=m=1$ และ $M_{1,1}=c$
คุณต้องดำเนินการ $q$ ครั้ง โดยแต่ละครั้งจะอยู่ในประเภทใดประเภทหนึ่งจากสามประเภทต่อไปนี้:
1 x y($0\le x\le n$, $1\le y\le 10^9$) แทรกแถวที่มีค่า $y$ ระหว่างแถวที่ $x$ และแถวที่ $(x+1)$ หลังจากดำเนินการนี้ $n$ จะเพิ่มขึ้น $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) แทรกคอลัมน์ที่มีค่า $y$ ระหว่างคอลัมน์ที่ $x$ และคอลัมน์ที่ $(x+1)$ หลังจากดำเนินการนี้ $m$ จะเพิ่มขึ้น $1$;3 x y($1\le x\le n$, $1\le y\le m$) สอบถามค่าของ $M_{x,y}$
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองจำนวนคือ $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$)
อีก $q$ บรรทัดถัดไป แต่ละบรรทัดอธิบายการดำเนินการหนึ่งครั้ง
จำนวนเต็มสามจำนวน $opt,x,y$ ที่จุดเริ่มต้นของแต่ละบรรทัด ($opt\in\{1,2,3\}$) มีความหมายตามที่อธิบายไว้ในโจทย์ด้านบน
ข้อมูลส่งออก
สำหรับการดำเนินการสอบถามแต่ละครั้ง ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งจำนวนแทนคำตอบ
ตัวอย่าง
ข้อมูลนำเข้า 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
ข้อมูลส่งออก 1
1 4 3