الوصف
لا يمكن أن تخلو مسابقة من مسألة هياكل بيانات، حتى لو كانت مجرد مسألة بالون سهلة.
تُعطى لك مصفوفة $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