{"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\u003cb\u003eIt is preferrable to read the pdf statment.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eCuber QQ is poor in English writing, and in the process of preparing this contest, he realized that he is making too many grammar mistakes that an auto-correction engine is needed. Instead of using online tools like \u0027\u0027Microsoft Aim Writing\u0027\u0027 or \u0027\u0027Grammarly\u0027\u0027, he was interested in building a new engine on his own.\u003cbr\u003e\u003cbr\u003eIn particular, he adopted a naive sequence-to-sequence model, that takes a sequence, which is usually a sentence, and predict for each token, which is usually a word or character, whether there is something wrong with it, and if yes, what it should be replaced with. Here are several examples:\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e In \u0027\u0027Cuber QQ was one of the admirers Quber CC.\u0027\u0027, \u0027\u0027admirers\u0027\u0027 should be replaced with \u0027\u0027admirers of\u0027\u0027.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e In \u0027\u0027Cuber QQ confess his love to Cuber QQ just now.\u0027\u0027, \u0027\u0027confess\u0027\u0027 should be replaced with \u0027\u0027confessed\u0027\u0027.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e In \u0027\u0027Quber CC said that they are being and always will be good friends.\u0027\u0027, \u0027\u0027are being\u0027\u0027 should be replaced with \u0027\u0027are\u0027\u0027.\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eYou might notice that, in this sequence-to-sequence model, the phrase to replace should be at least one token, and the target should be at least one token too. This is related to the architecture and training approach of his model. We will not go into too many machine learning details here, as it will make the statement tedious. The problem is however, the training data does not conform with such format. In the training data, a sequence with flaws can be annotated with three types of annotations: add, delete and replace. Concretely,\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e $A$ $l$ $s_1$ $s_2$ $\\cdots$ $s_v$: to add sequence $s$ before position $l$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $D$ $l$ $r$: to delete from $l$-th token to the $r$-th token, inclusive.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $R$ $l$ $r$ $s_1$ $s_2$ $\\cdots$ $s_v$: to replace sub-sequence from $l$-th token to $r$-th token, inclusive, with sequence $s$.\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eAll the annotations are applied directly to the original sequence, i.e., the indices like $l$ and $r$ refers to the original indices, instead of the indices after modification.\u003cbr\u003e\u003cbr\u003eAs \u0027\u0027add\u0027\u0027 and \u0027\u0027delete\u0027\u0027 will not be supported in the model, the preprocessing step needs to rewrite all \u0027\u0027add\u0027\u0027 and \u0027\u0027delete\u0027\u0027 with \u0027\u0027replace\u0027\u0027. Furthermore, as there are many ways to achieve such goal, Cuber QQ wants to find the cheapest way, i.e., after the annotation rewriting, the total number of replaced tokens should be as minimum as possible. If there is a tie, the number of annotation records should be as minimum as possible. In case there is still a tie, any one of them is acceptable.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input starts with an integer $t$ ($1 \\le T \\le 50~000$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two space-separated integers $n$ and $q$ ($1 \\le n, q \\le 2~000$), where $n$ is the number of tokens in the original sequence, and $q$ is the number of original annotations.\u003cbr\u003e\u003cbr\u003eIn the next line, $n$ integers $a_1, a_2, \\ldots, a_n$ ($1 \\le a_i \\le n$) are presented, denoting the sequence.\u003cbr\u003e\u003cbr\u003eThe $i$-th of the following $q$ lines is in one of the 3 formats:\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e $A$ $l_i$ $s_{i,1}$ $s_{i,2}$ $\\cdots$ $s_{i,{v_i}}$ ($1 \\le l_i \\le n + 1$, $1 \\le s_{i,k} \\le n$). Notably, when $l_i \u003d n + 1$, it is to add tokens at the end of sequence.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $D$ $l_i$ $r_i$ ($1 \\le l_i \\le r_i \\le n$).\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $R$ $l_i$ $r_i$ $s_{i,1}$ $s_{i,2}$ $\\cdots$ $s_{i,{v_i}}$ ($1 \\le l_i \\le r_i \\le n$, $1 \\le s_{i,k} \\le n$).\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eIt is guaranteed that $l_i \\le l_{i+1}$ for all $1 \\le i \u0026lt; n$, and $l_i \u003d l_{i+1}$ only happens when $i$ is $A$ and $i+1$ is not, which means, there is at most one \u0027\u0027add\u0027\u0027 at the same position. The annotations are non-overlapping, i.e., $r_i \\le l_{i+1}$ for all $1 \\le i \u0026lt; n$ if $r_i$ is available for $i$. Furthermore, the corrected sequence after applying all the annotations is not empty.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that for each test case, the corrected sequence is neither empty nor longer than $4~000$. The sum of $n$ and the total length of corrected sequences both do not exceed $50~000$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, in the first line output two space-separated integers: minimum number of tokens that will be replaced, $x$, and minimum number of converted annotations, $y$.\u003cbr\u003e\u003cbr\u003eIn the following $y$ lines, you can output the annotations in any order. $R$ should be omitted as it is the only type that is allowed. The annotations should be non-overlapping, non-empty and follow the exactly same format as input.\u003cbr\u003e\u003cbr\u003e\u003ch3\u003eNote\u003c/h3\u003e\u003cbr\u003eFor the first test case, $[2, 3]$ is replaced with $1$, $[4, 6]$ is replaced with $2,3$, and the corrected sequence is $1,1,2,3$. The optimal correction with only $R$ is to replace $[2, 6]$ with $1,2,3$.\u003cbr\u003e\u003cbr\u003eFor the second test case, the corrected sequence is $1,2,4,6,5$. Although $A$ and $D$ cannot be used, if we merge the consecutive annotations, only 4 tokens need to be replaced.\u003cbr\u003e\u003cbr\u003eIn the third test case, we show that the corrected sequence can be longer than the original sequence, which is $2,1,2,3,4,5,5,6$."}},{"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\u003e3\r\n6 2\r\n1 2 5 3 4 6\r\nR 2 3 1\r\nR 4 6 2 3\r\n6 3\r\n1 2 2 3 4 6\r\nR 3 4 4\r\nD 5 5\r\nA 7 5\r\n6 2\r\n1 2 3 4 5 6\r\nA 1 2\r\nA 6 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5 1\r\n2 6 1 2 3\r\n4 1\r\n3 6 4 6 5\r\n2 2\r\n6 6 5 6\r\n1 1 2 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}