Description

In the 21^st century, many people have a strange disease: difficulty getting up syndrome; the clinical manifestations of which are: difficulty getting up and poor spirits after getting up. As a young and sunny boy, Bob has always struggled with the difficulty waking up syndrome. By studying relevant literature, he found the cause of the disease: in the deep Pacific Ocean, a giant dragon named Drago has appeared, who holds the essence of sleep and can prolong everyone's sleep time at will. It is precisely because of Drago's activities that the difficulty waking up syndrome has intensified and spread around the world at an alarming rate. In order to completely eradicate this disease, Bob decided to go to the bottom of the sea and destroy this evil dragon.

After untold hardships, Bob finally came to the place where Drago was, ready to start an arduous battle with it. Drago has very special skills, his defensive front can use certain calculations to change the damage he receives. Specifically, the defensive front of Drago is composed of $n$ defensive doors. Each defensive door includes an operation $\mathrm{op}$ and a parameter $t$. The operation is one of OR , XOR , AND , and the parameter is a non-negative integer. If you have not passed the defensive door, and your attack's power is $x$, then the attack's power will become $x~\mathrm{op}~t$ after crossing the door. The final damage received by Drago is the final resulting power of Bob’s initial attack with power $x$ after going through all $n$ defensive doors (each door will transform this power according to the operation).

Due to the limited level of Bob, his initial attack's power can only be in the range $[0, m]$ (that is, his initial attack's power can only be $0, 1, \dots, m$, but the attack power after passing through the defensive gate is not limited by $m$). In order to save energy, he hopes to deal maximum damage to Drago by choosing a suitable initial attack's power. Please help him calculate the maximum damage he can cause Drago with one attack.

Input Format

The first line contains two integers $n$ and $m$, which means that Drago has $n$ defensive doors and Bob's initial attack's power is an integer in the range $[0, m]$ (inclusive). This is followed by $n$ rows, indicating each defensive door in order of occurence. Each line contains a string $\mathrm{op}$ and a non-negative integer $t$, separated by a space, where $\mathrm{op}$ indicates the operation corresponding to the defensive door and $t$ indicates the corresponding parameter.

Output Format

One integer which is the maximum damage Bob can cause to Drago.

3 10
AND 5
OR 6
XOR 7

1

Constraints

For all test points,$0 \leq t \lt 2^{30}$ and $\mathrm{op}$ is one of OR, XOR, AND.

NOTE:

In this question, the contestant needs to convert the numbers to binary before performing calculations. If the binary lengths of the two numbers of the operation are different, first insert $0$'s to make the lengths same.

• OR is a bitwise OR operation, processing two binary numbers of the same length, as long as one of the two corresponding binary bits is $1$, the result value of this bit is $1$, Otherwise $0$.
• XOR is a bitwise exclusive OR operation, which performs a logical exclusive OR operation on each bit of the equal-length binary number. If the two corresponding binary bits are different, the result value of that bit is $1$, Otherwise the bit is $0$.
• AND is a bitwise AND operation, which processes two binary numbers of the same length, and if the two corresponding binary digits are both $1$, the result value of this bit is $1$, Otherwise $0$.

For example, we will set the decimal number $5$ with decimal numbers $3$, perform OR , XOR, and AND operations separately, and you can get the following results:

    0101 (Binary representation of 5)
 OR 0011 (Binary representation of 3)
  = 0111 (Binary representation of 7)

    0101 (Binary representation of 5)
XOR 0011 (Binary representation of 3)
  = 0110 (Binary representation of 6)

    0101 (Binary representation of 5)
AND 0011 (Binary representation of 3)
  = 0001 (Binary representation of 1)