{"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度度熊正在学习双端队列,他对其翻转和合并产生了很大的兴趣。\u003cbr\u003e\u003cbr\u003e初始时有 $N$ 个空的双端队列(编号为 $1$ 到 $N$ ),你要支持度度熊的 $Q$ 次操作。\u003cbr\u003e\u003cbr\u003e①$1$ $u$ $w$ $val$ 在编号为 $u$ 的队列里加入一个权值为 $val$ 的元素。($w\u003d0$ 表示加在最前面,$w\u003d1$ 表示加在最后面)。\u003cbr\u003e\u003cbr\u003e②$2$ $u$ $w$ 询问编号为 $u$ 的队列里的某个元素并删除它。( $w\u003d0$ 表示询问并操作最前面的元素,$w\u003d1$ 表示最后面)\u003cbr\u003e\u003cbr\u003e③$3$ $u$ $v$ $w$ 把编号为 $v$ 的队列“接在”编号为 $u$ 的队列的最后面。$w\u003d0$ 表示顺序接(队列 $v$ 的开头和队列 $u$ 的结尾连在一起,队列$v$ 的结尾作为新队列的结尾), $w\u003d1$ 表示逆序接(先将队列 $v$ 翻转,再顺序接在队列 $u$ 后面)。且该操作完成后,队列 $v$ 被清空。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"有多组数据。\u003cbr\u003e\u003cbr\u003e对于每一组数据,第一行读入两个数 $N$ 和 $Q$。\u003cbr\u003e\u003cbr\u003e接下来有 $Q$ 行,每行 $3$~$4$ 个数,意义如上。\u003cbr\u003e\u003cbr\u003e$N \\leq 150000,Q \\leq 400000$\u003cbr\u003e\u003cbr\u003e$1 \\leq u,v \\leq N,0 \\leq w \\leq 1,1 \\leq val \\leq 100000$\u003cbr\u003e\u003cbr\u003e所有数据里 $Q$ 的和不超过$500000$\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于每组数据的每一个操作②,输出一行表示答案。\u003cbr\u003e\u003cbr\u003e注意,如果操作②的队列是空的,就输出$-1$且不执行删除操作。"}},{"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\u003e2 10\r\n1 1 1 23\r\n1 1 0 233\r\n2 1 1 \r\n1 2 1 2333\r\n1 2 1 23333\r\n3 1 2 1\r\n2 2 0\r\n2 1 1\r\n2 1 0\r\n2 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e23\r\n-1\r\n2333\r\n233\r\n23333\r\n\r\n提示\r\n\r\n由于读入过大,C/C++ 选手建议使用读入优化。\r\n\r\n一个简单的例子:\r\n\r\nvoid read(int \u0026amp;x){\r\n\tchar ch \u003d getchar();x \u003d 0;\r\n\tfor (; ch \u0026lt; \u00270\u0027 || ch \u0026gt; \u00279\u0027; ch \u003d getchar());\r\n\tfor (; ch \u0026gt;\u003d\u00270\u0027 \u0026amp;\u0026amp; ch \u0026lt;\u003d \u00279\u0027; ch \u003d getchar()) x \u003d x * 10 + ch - \u00270\u0027;\r\n}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}