{"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发明了一种新型计算器,可以评估表达式。这个计算器内部维护着一系列的运算符和数字。所有这些数字和运算符形成了一个有序表。例如\u003cbr\u003e\u003cbr\u003e$*4 \\quad + 2 \\quad \\hat{} 3 \\quad + 8 \\quad * 6$\u003cbr\u003e\u003cbr\u003e是一个可能的表。该计算器还支持以下两种操作。\u003cbr\u003e\u003cbr\u003e1. 1 $x$。\u003cbr\u003e\u003cbr\u003e这对应于评估操作。例如,如果$x\u003d2$,以及表格是上述描述的表格,计算器将输出\u003cbr\u003e\u003cbr\u003e$ ((((2*4)+2)^3)+8)*6\u003d6048.$\u003cbr\u003e\u003cbr\u003e而对于$x\u003d3$,它将输出\u003cbr\u003e\u003cbr\u003e$((((3*4)+2)^3)+8)*6\u003d16512.$\u003cbr\u003e\u003cbr\u003e2. 2 $p$ $cx$。\u003cbr\u003e\u003cbr\u003e这对应于修改操作。计算器将把表达式中的第$p$个项更改为$cx$。这里$c$表示一个运算符,而$x$表示一个数字。\u003cbr\u003e\u003cbr\u003e例如,如果$p\u003d3$和$cx\u003d*5$,表达式将变为\u003cbr\u003e\u003cbr\u003e$*4 \\quad + 2 \\quad *5 \\quad + 8 \\quad * 6.$\u003cbr\u003e\u003cbr\u003e现在要求你实现这个计算器。但是,由于技术原因,你应该只输出结果模29393。保证,在输入数据中出现的所有项中,$c \\in \\{+, *, \\hat{} \\}$,$0 \\le x \u0026lt; 29393$。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数$T$($T \\le 10$),表示测试用例的数量。保证$1 \\le n, m \\le 50000$。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,第一行包含两个数字$n, m$。$n$表示表达式中的项数,$m$表示操作数。\u003cbr\u003e\u003cbr\u003e在接下来的$n$行中,每行包含一个样式为$cx$的项,表示初始表中的每个项。\u003cbr\u003e\u003cbr\u003e在接下来的$m$行中,每行包含一个操作。它必须是\u0027\u0027$1 \\quad x$\u0027\u0027或\u0027\u0027$2\\quad p \\quad cx$\u0027\u0027的样式。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出Case #t: 以一行表示第$t$个案例。\u003cbr\u003e然后在每个测试用例中,输出每个评估操作的结果模29393。\u003cbr\u003e"}},{"title":"示例","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"}}]}