{"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\"\u003eSakura has invented a new kind of calculator that can evaluate expressions. This calculator maintains a serial of operators and numbers inside. All these numbers and operators form an ordered table. For example\u003cbr\u003e\u003cbr\u003e$*4 \\quad + 2 \\quad \\hat{} 3 \\quad + 8 \\quad * 6$\u003cbr\u003e\u003cbr\u003eis a possible table. The calculator also supports the following two operations.\u003cbr\u003e\u003cbr\u003e1. 1 $x$.\u003cbr\u003e\u003cbr\u003eThis corresponds to the evaluation operation. For instance, if $x\u003d2$, together with the table being the one described above, the calculator will output\u003cbr\u003e\u003cbr\u003e$ ((((2*4)+2)^3)+8)*6\u003d6048.$\u003cbr\u003e\u003cbr\u003eAs for $x\u003d3$, it will output\u003cbr\u003e\u003cbr\u003e$((((3*4)+2)^3)+8)*6\u003d16512.$\u003cbr\u003e\u003cbr\u003e2. 2 $p$ $cx$.\u003cbr\u003e\u003cbr\u003eThis corresponds to the modification operation. The calculator will change the $p$-th term in the expression to $cx$. Here $c$ denotes an operator while $x$ denotes a number.\u003cbr\u003e\u003cbr\u003eFor example, if $p\u003d3$ and $cx\u003d*5$, the expression will become\u003cbr\u003e\u003cbr\u003e$*4 \\quad + 2 \\quad *5 \\quad + 8 \\quad * 6.$\u003cbr\u003e\u003cbr\u003eNow you are asked to implement this calculator. However, for technical reasons, you should just output the result modulo 29393. It is guaranteed that, in all terms appeared in the input data, $c \\in \\{+, *, \\hat{} \\}$, $0 \\le x \u0026lt; 29393$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$($T \\le 10$), denoting the number of test cases. It is guaranteed that $1 \\le n, m \\le 50000$.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two numbers $n, m$. $n$ denotes the number of terms in the expression, $m$ denotes the number of operations.\u003cbr\u003e\u003cbr\u003eIn the following $n$ lines, each line contains a term in style of $cx$, denotes each term in the initial table.\u003cbr\u003e\u003cbr\u003eIn the following $m$ lines, each line contains an operation. It must in style of \u0027\u0027$1 \\quad x$\u0027\u0027 or \u0027\u0027$2\\quad p \\quad cx$\u0027\u0027.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output Case #t: in a single line to represent the $t$-th case.\u003cbr\u003eThen in each test case, output the result modulo 29393 for each evaluation operation.\u003cbr\u003e"}},{"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\r\n5 4\r\n*4\r\n+2\r\n^3\r\n+8\r\n*6\r\n1 2\r\n1 3\r\n2 3 *5\r\n1 3\r\n4 3\r\n*4\r\n^4\r\n+4\r\n*10\r\n1 1\r\n2 3 ^4\r\n1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n6048\r\n16512\r\n468\r\nCase #2:\r\n2600\r\n4107\r\nP\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}