תיאור
תחרות לא יכולה להתקיים ללא בעיית מבני נתונים, גם אם זו רק בעיית בלון.
נתונה לכם מטריצה $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