P2114 [NOI2014] Wake-Up Difficulty Syndrome

In the 21st century, many people have developed a strange illness: the Wake-Up Difficulty Syndrome, whose clinical symptoms are: difficulty getting up and poor mental state after getting up. As a sunny and energetic teenager, atm has always fought against this syndrome. By studying relevant literature, he discovered the cause of the illness: deep under the Pacific Ocean, there is a giant dragon named drd, who masters the essence of sleep and can arbitrarily extend everyone’s sleep time. It is precisely due to drd’s activities that the Wake-Up Difficulty Syndrome has worsened and is spreading at an alarming rate around the world. To completely eliminate this disease, atm decides to go to the seabed to defeat this evil dragon. After enduring many hardships, atm finally arrives at drd’s location, ready for a tough and arduous battle. drd has a very special skill: his defensive front can use certain operations to change the damage he receives. Specifically, drd’s defensive front consists of $n$ defense gates. Each defense gate includes an operation $\text{op}$ and a parameter $t$, where the operation must be one of $\texttt{OR}, \texttt{XOR}, \texttt{AND}$, and the parameter must be a non-negative integer. If the attack power before passing the gate is $x$, then after passing this gate it becomes $x\,\text{op}\,t$. The final damage drd receives is the attack power obtained by applying all $n$ defense gates in order to the opponent’s initial attack power $x$. Because atm’s ability is limited, his initial attack power can only be an integer between $0$ and $m$ (that is, he can choose his initial attack power from $0, 1, \ldots, m$, but the attack power after passing through the defense gates is not limited by $m$). To save energy, he wants to choose a suitable initial attack power so that his attack causes the maximum possible damage to drd. Please help him compute the maximum damage his single attack can cause.

The first line of the input file contains $2$ integers, $n, m$, indicating that drd has $n$ defense gates, and atm’s initial attack power can be any integer from $0$ to $m$. The next $n$ lines describe each defense gate in order. Each line contains a string $\text{op}$ and a non-negative integer $t$, separated by a space, with $\text{op}$ first and $t$ second. $\text{op}$ denotes the operation of the defense gate, and $t$ denotes its parameter.

Output a single integer on one line: the maximum damage that atm’s single attack can cause to drd.

【Sample Explanation】 atm can choose an initial attack power from $0, 1, \ldots, 10$. Suppose the initial attack power is $4$. The final attack power is computed as follows: - $4 \texttt{ AND } 5 = 4$; - $4 \texttt{ OR } 6 = 6$; - $6 \texttt{ XOR } 7 = 1$. Similarly, we can compute that when the initial attack power is $1, 3, 5, 7, 9$, the final attack power is $0$; when the initial attack power is $0, 2, 4, 6, 8, 10$, the final attack power is $1$. Therefore, the maximum damage atm’s single attack can cause to drd is $1$. 【Constraints and Conventions】  - Special property $\mathrm A$: There exists a defense gate equal to $\texttt{AND}~0$. - Special property $\mathrm B$: All defense gates use the same operation. For all testdata, it is guaranteed that $2 \le n \le 10^5$, $0 \le m \le 10^9$, $0 \le t \le 10^9$, and $\mathrm{op}$ is one of $\verb!AND!,\verb!OR!,\verb!XOR!$. Translated by ChatGPT 5