Сипаттамасы
Жарыс деректер құрылымына арналған есепсіз болмайды, тіпті ол жай ғана шар беретін оңай есеп болса да.
Сізге $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$) $x$-ші жол мен $(x+1)$-ші жолдың арасына мәні $y$ болатын жол кірістіру; осы амалдан кейін $n$ мәні $1$-ге артады;2 x y($0\le x\le m$, $1\le y\le 10^9$) $x$-ші баған мен $(x+1)$-ші бағанның арасына мәні $y$ болатын баған кірістіру; осы амалдан кейін $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