Description
Un concours ne peut pas se passer d'un problème de structures de données, même s'il ne s'agit que d'un problème ballon.
On vous donne une matrice $M$. Soit $M_{i,j}$ l'élément situé à la $i$-ème ligne et la $j$-ème colonne de la matrice, et soient $n$ et $m$ le nombre de lignes et de colonnes respectivement. Initialement, $n=m=1$, et $M_{1,1}=c$.
Vous devez effectuer $q$ opérations, chacune appartenant à l'un des trois types suivants :
1 x y($0\le x\le n$, $1\le y\le 10^9$) insérer une ligne de valeur $y$ entre la $x$-ème ligne et la $(x+1)$-ème ligne ; après cette opération, $n$ augmente de $1$ ;2 x y($0\le x\le m$, $1\le y\le 10^9$) insérer une colonne de valeur $y$ entre la $x$-ème colonne et la $(x+1)$-ème colonne ; après cette opération, $m$ augmente de $1$ ;3 x y($1\le x\le n$, $1\le y\le m$) demander la valeur de $M_{x,y}$.
Entrée
La première ligne de l'entrée contient deux entiers $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Les $q$ lignes suivantes décrivent chacune une opération.
Les trois entiers $opt,x,y$ au début de chaque ligne ($opt\in\{1,2,3\}$) ont la signification décrite dans l'énoncé ci-dessus.
Sortie
Pour chaque opération de requête, affichez une ligne contenant un entier représentant la réponse.
Exemples
Entrée 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Sortie 1
1 4 3