{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program, whether the program will finish running (i.e., halt) or continue to run forever.\u003c/p\u003e\n\n\u003cp\u003eAlan Turing proved in 1936 that a general algorithm to solve the halting problem cannot exist, but DreamGrid, our beloved algorithm scientist, declares that he has just found a solution to the halting problem in a specific programming language -- the Dream Language!\u003c/p\u003e\n\n\u003cp\u003eDream Language is a programming language consists of only 5 types of instructions. All these instructions will read from or write to a 8-bit register $r$, whose value is initially set to 0. We now present the 5 types of instructions in the following table. Note that we denote the current instruction as the $i$-th instruction.\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInstruction\u003c/th\u003e\n \u003cth\u003eDescription\u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003eadd $v$\u003c/td\u003e\n \u003ctd\u003eAdd $v$ to the register $r$. As $r$ is a 8-bit register, this instruction actually calculates $(r + v) \\mod 256$ and stores the result into $r$, i.e. $r \\leftarrow (r + v) \\mod 256$. After that, go on to the $(i + 1)$-th instruction.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003ebeq $v$ $k$\u003c/td\u003e\n \u003ctd\u003eIf the value of $r$ is equal to $v$, jump to the $k$-th instruction, otherwise go on to the $(i + 1)$-th instruction.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003ebne $v$ $k$\u003c/td\u003e\n \u003ctd\u003eIf the value of $r$ isn\u0027t equal to $v$, jump to the $k$-th instruction, otherwise go on to the $(i + 1)$-th instruction.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003eblt $v$ $k$\u003c/td\u003e\n \u003ctd\u003eIf the value of $r$ is strictly smaller than $v$, jump to the $k$-th instruction, otherwise go on to the $(i + 1)$-th instruction.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003ebgt $v$ $k$\u003c/td\u003e\n \u003ctd\u003eIf the value of $r$ is strictly larger than $v$, jump to the $k$-th instruction, otherwise go on to the $(i + 1)$-th instruction.\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eA Dream Language program consisting of $n$ instructions will always start executing from the 1st instruction, and will only halt (that is to say, stop executing) when the program tries to go on to the $(n + 1)$-th instruction.\u003c/p\u003e\n\n\u003cp\u003eAs DreamGrid\u0027s assistant, in order to help him win the Turing Award, you are asked to write a program to determine whether a given Dream Language program will eventually halt or not.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^4$), indicating the number of instructions in the following Dream Language program.\u003c/p\u003e\n\n\u003cp\u003eFor the following $n$ lines, the $i$-th line first contains a string $s$ ($s \\in \\{\\text{\"add\"}, \\text{\"beq\"}, \\text{\"bne\"}, \\text{\"blt\"}, \\text{\"bgt\"}\\}$), indicating the type of the $i$-th instruction of the program.\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cp\u003eIf $s$ equals to \"add\", an integer $v$ follows ($0 \\le v \\le 255$), indicating the value added to the register;\u003c/p\u003e\u003c/li\u003e\n \u003cli\u003e\u003cp\u003eOtherwise, two integers $v$ and $k$ follow ($0 \\le v \\le 255$, $1 \\le k \\le n$), indicating the condition value and the destination of the jump.\u003c/p\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line. If the program will eventually halt, output \"Yes\" (without quotes); If the program will continue to run forever, output \"No\" (without quotes).\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e4\n2\nadd 1\nblt 5 1\n3\nadd 252\nadd 1\nbgt 252 2\n2\nadd 2\nbne 7 1\n3\nadd 1\nbne 252 1\nbeq 252 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYes\nYes\nNo\nNo\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the second sample test case, note that $r$ is a 8-bit register, so after four \"add 1\" instructions the value of $r$ will change from 252 to 0, and the program will halt.\u003c/p\u003e\n\n\u003cp\u003eFor the third sample test case, it\u0027s easy to discover that the value of $r$ will always be even, so it\u0027s impossible for the value of $r$ to be equal to 7, and the program will run forever.\u003c/p\u003e\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n}\n\u003c/style\u003e\n"}}]}