{"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\"\u003eOops, there is something wrong with the Pandaemonium. The friend of Azem, Themis, is just waiting for you to have a look together.\u003cbr\u003e\u003cbr\u003eOh no, rattled Erichthonios, who is the guard of Pandaemonium, misunderstanding you as enemies, starts attacking you. Can you protect yourself and Themis until he calms down?\u003cbr\u003e\u003cbr\u003eTo simplify the problem, Themis\u0027 defending system have $n$ blocks in a line. All the blocks have a initial weight 0 and the same attribute. Erichthonios will perform following 4 kinds of attack $q$ times:\u003cbr\u003e\u003cbr\u003e - $1$ $x$ $c$: Erichthonios uses his chain to connect the $x$-th block and all $\\bf{closest}$ $2c$ blocks, giving them a new attribute (overlapping the origin atrributes of the blocks).\u003cbr\u003e - $2$ $x$ $y$: Erichthonios copies the attribute of $x$-th block to $y$-th and all $y$-th block\u0027s $\\bf{nearby}$, $\\bf{continuous}$, $\\bf{same\\ attribute}$, $\\bf{longest}$ blocks. (A segment of same attribute blocks containing $y$-th, and the left adjacent block of the segment has a different attribute or is out of boundary, so as right.)\u003cbr\u003e - $3$ $x$ $v$: Erichthonios makes the weight of all the blocks with the same attribute as $x$-th block increase by $v$.\u003cbr\u003e - $4$ $x$: Erichthonios attacks the defending system. Only if you output the weight of the $x$-th block, can you defend it.\u003cbr\u003e\u003cbr\u003eAttention: Since you don\u0027t know what Erichthonios will do next, there is encoding with the queries. (See the $\\bf{input}$)\u003cbr\u003e\u003cbr\u003eIf you couldn\u0027t solve this problem, you will be laughed at by Hythlodaeus later. You don\u0027t want to be like that, right?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Each test contains multiple test cases. The first line contains the number of test cases $(1 \\le T \\le 20)$. Description of the test cases follows.\u003cbr\u003e\u003cbr\u003eThe first line contains two integers $n$ and $q$ ($3\\leq n\\leq10^8$, $1\\leq q\\leq 10^5$) -- The number of Themis defending system blocks, and the number of attacks that Erichthonios will perform.\u003cbr\u003e\u003cbr\u003eThe following $q$ lines contains Erichthonios\u0027 attacks, (initially, $last \u003d 0$):\u003cbr\u003e\u003cbr\u003e - $1$ $x\u0027$ $c\u0027$: contains 3 integers, $1\\leq x\u0027\\leq n$, $1 \\leq c\u0027 \\leq \\lfloor\\frac{n-1}{2}\\rfloor$, actually, $x \u003d \\big((x\u0027 - 1) \\oplus last\\big) \\mod n\\ +\\ 1$, $c \u003d \\big((c\u0027 - 1) \\oplus last\\big) \\mod \\lfloor\\frac{n-1}{2}\\rfloor\\ +\\ 1$.\u003cbr\u003e - $2$ $x\u0027$ $y\u0027$: contains 3 integers, $1\\leq x\u0027\\leq n$, $1 \\leq y\u0027 \\leq n$, actually, $x \u003d \\big((x\u0027 - 1) \\oplus last\\big) \\mod n\\ +\\ 1$, $y \u003d \\big((y\u0027 - 1) \\oplus last\\big) \\mod n\\ +\\ 1$.\u003cbr\u003e - $3$ $x\u0027$ $v$: contains 3 integers, $1\\leq x\u0027\\leq n$, $1 \\leq v \\leq 10^9$, actually, $x \u003d \\big((x\u0027 - 1) \\oplus last\\big) \\mod n\\ +\\ 1$, and there is no encode with $v$, $1 \\leq v \\leq 10^9$.\u003cbr\u003e - $4$ $x\u0027$: contains 2 integers, $1\\leq x\u0027\\leq n$, actually, $x \u003d \\big((x\u0027 - 1) \\oplus last\\big) \\mod n\\ +\\ 1$, after you get the $Answer$, don\u0027t forget to update, $last \u003d Answer\\ \\text{and}\\ 1\\ 073\\ 741\\ 823$.\u003cbr\u003e\u003cbr\u003eWhere $\\oplus$ means bitwise XOR operation, $\\text{and}$ means bitwise AND operation.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the sum of $n$ does not exceed $2\\cdot 10^9$ and the sum of $q$ does not exceed $10^6$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case:\u003cbr\u003e\u003cbr\u003eFor each $4$-th attack, print one integer in a line --- the weight of the block."}},{"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\u003e1\r\n16 12\r\n3 10 16\r\n4 2\r\n1 1 6\r\n1 5 6\r\n1 9 7\r\n1 15 7\r\n2 2 10\r\n2 2 13\r\n3 1 16\r\n4 16\r\n4 9\r\n4 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\r\n32\r\n32\r\n16\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eThe decoded attacks in example:\u003cbr\u003e\u003cbr\u003e3, x \u003d 10 , v \u003d 16\u003cbr\u003e\u003cbr\u003e4, x \u003d 2\u003cbr\u003e\u003cbr\u003e1, x \u003d 1 , c \u003d 1\u003cbr\u003e\u003cbr\u003e1, x \u003d 5 , c \u003d 1\u003cbr\u003e\u003cbr\u003e1, x \u003d 9 , c \u003d 2\u003cbr\u003e\u003cbr\u003e1, x \u003d 15 , c \u003d 2\u003cbr\u003e\u003cbr\u003e2, x \u003d 2 , y \u003d 10\u003cbr\u003e\u003cbr\u003e2, x \u003d 2 , y \u003d 13\u003cbr\u003e\u003cbr\u003e3, x \u003d 1 , v \u003d 16\u003cbr\u003e\u003cbr\u003e4, x \u003d 16\u003cbr\u003e\u003cbr\u003e4, x \u003d 9\u003cbr\u003e\u003cbr\u003e4, x \u003d 4\u003cbr\u003e"}}]}