{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ci\u003e\"Why don\u0027t you write some background story for this boring data structure problem?\"\u003c/i\u003e\u003cbr\u003e\u003ci\u003e\"Because it\u0027s too boring...\"\u003c/i\u003e\u003cbr\u003e\u003cbr\u003eThere\u0027s a queue(not the original queue one may refer to as a data structure, here a double-ended queue, to be more precise) that is initially empty. Then, there are infinite elements numbered $1,2,\\dots$, entering the queue in the order of their numbers(i.e., the first element to enter the queue is numbered $1$, the second, $2$ et cetera). If an element leaves the queue, it will not enter the queue anymore.\u003cbr\u003e\u003cbr\u003eNow there are $q$ operations, each in one of the following forms:\u003cbr\u003e\u003cul\u003e\u003cli\u003e Let the next element enter the left end of the queue. \u003c/li\u003e\u003cbr\u003e\u003cli\u003e Let the next element enter the right end of the queue. \u003c/li\u003e\u003cbr\u003e\u003cli\u003e Let the element numbered $x$ leave the queue. \u003c/li\u003e\u003cbr\u003e\u003cli\u003e Ask the number of the element in the middle of the queue. (If there are $m$ elements in the queue currently, you should output the number of the element that is the $\\lceil \\frac{m+1}{2} \\rceil$th from the left). \u003c/li\u003e\u003c/ul\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of each test case contains one number $q(1\\leq q \\leq 10^7)$, denoting the number of operations.\u003cbr\u003e\u003cbr\u003eThen $q$ lines follow, each in one of the following forms:\u003cbr\u003e\u003cul\u003e\u003cli\u003e $L$, denoting the next element enters the left end of the queue \u003c/li\u003e\u003cbr\u003e\u003cli\u003e $R$, denoting the next element enters the right end of the queue \u003c/li\u003e\u003cbr\u003e\u003cli\u003e $G$ $x$, denoting the element numbered $x$ leaves the queue (It is guaranteed that the element numbered $x$ is in the queue when this operation is applied) \u003c/li\u003e\u003cbr\u003e\u003cli\u003e $Q$ denoting a query that asks the number of the element in the middle of the queue(It is guaranteed that the queue is not empty when this operation is applied) \u003c/li\u003e\u003c/ul\u003e\u003cbr\u003eIt is guaranteed that the number of operations of the third and the fourth type is both less than $1.5\\cdot 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For each operation of the fourth kind, output a number in a line, denoting the answer to the query."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\nL\r\nL\r\nL\r\nQ\r\nR\r\nQ\r\nG 1\r\nR\r\nQ\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}