In the 21st century, many people have contracted a strange disease: "Getting-up-difficulty Syndrome." Its clinical symptoms include difficulty getting up and feeling lethargic after waking up. As a young, energetic, and positive teenager, atm has been fighting against this syndrome. Through research into relevant literature, he found the cause of the disease: in the depths of the Pacific Ocean, there is a giant dragon named drd. It possesses the essence of sleep and can extend everyone's sleep time at will. It is precisely because of drd's activities that the Getting-up-difficulty Syndrome has intensified and spread across the world at an alarming rate. To completely eradicate this disease, atm decided to head to the ocean floor to destroy this evil dragon.

After much hardship, atm finally arrived at the place where drd resides, preparing to engage in a grueling battle. drd has a very special skill: its defensive line can use certain operations to change the damage it receives. Specifically, drd's defensive line consists of $n$ defensive gates. Each defensive gate includes an operation $op$ and a parameter $t$, where the operation is one of OR, XOR, or AND, and the parameter is a non-negative integer. If the attack power before passing through a defensive gate is $x$, the attack power after passing through this gate becomes $x \text{ op } t$. The final damage received by drd is the attack power obtained after the initial attack power passes through all $n$ defensive gates in sequence.

Since atm's level is limited, his initial attack power can only be an integer between $0$ and $m$ (i.e., his initial attack power can be chosen from $0, 1, \dots, m$, but the attack power after passing through the defensive gates is not limited by $m$). To save energy, he hopes to choose an appropriate initial attack power so that his attack can cause the maximum damage to drd. Please help him calculate the maximum damage he can cause to drd in a single attack.

Input

The first line contains two integers $n$ and $m$, representing that drd has $n$ defensive gates, and atm's initial attack power is an integer between $0$ and $m$.

The next $n$ lines each represent a defensive gate. Each line includes a string $op$ and a non-negative integer $t$, separated by a space, with $op$ first and $t$ second. $op$ represents the operation corresponding to the defensive gate, and $t$ represents the corresponding parameter.

Output

Output a single integer representing the maximum damage atm can cause to drd in a single attack.

Examples

Input 1

3 10
AND 5
OR 6
XOR 7

Output 1

1

Note 1

atm can choose an initial attack power from $0, 1, \dots, 10$. Assuming the initial attack power is $4$, the final attack power is calculated as follows: $4 \text{ AND } 5 = 4$ $4 \text{ OR } 6 = 6$ $6 \text{ XOR } 7 = 1$ Similarly, we can calculate that if the initial attack power is $1, 3, 5, 7, 9$, the final attack power is $0$; if the initial attack power is $0, 2, 4, 6, 8, 10$, the final attack power is $1$. Therefore, the maximum damage atm can cause to drd in a single attack is $1$.

Constraints

Implementation Details

In this problem, participants need to convert numbers into binary before performing calculations. If the two numbers being operated on have different binary lengths, pad the shorter one with leading zeros to the same length.

OR is a bitwise OR operation. For two binary numbers of the same length, if either of the corresponding binary bits is $1$, the result for that bit is $1$, otherwise it is $0$. XOR is a bitwise XOR operation. It performs a logical XOR operation on each bit of the binary patterns or numbers of equal length. If two corresponding binary bits are different, the result for that bit is $1$, otherwise it is $0$. AND is a bitwise AND operation. For two binary numbers of the same length, the result for a bit is $1$ only if both corresponding binary bits are $1$, otherwise it is $0$.

For example, performing OR, XOR, and AND operations on the decimal numbers $5$ and $3$:

$0101$ (decimal $5$) $\text{OR } 0011$ (decimal $3$) $= 0111$ (decimal $7$)

$0101$ (decimal $5$) $\text{XOR } 0011$ (decimal $3$) $= 0110$ (decimal $6$)

$0101$ (decimal $5$) $\text{AND } 0011$ (decimal $3$) $= 0001$ (decimal $1$)