National Olympiad in Informatics, China, 2014
In the 21st century, many people have contracted an odd disorder – gettingup syndrome. Symptoms include having great difficulty getting out of bed in the morning and feeling out of sorts even after getting up. As a generally highspirited teenager, ATM has been struggling with gettingup syndrome. Through extensive research, he has found the cause of the disorder. On the vast seabeds of the Pacific Ocean, there lives a giant dragon by the name of DRD who holds the essence of sleep itself and can extend everyone's sleeping time at his will. So with DRD's every movement, gettingup syndrome intensifies for everyone, growing at a frightening rate to affect more and more people in the world. To put an end to this terrible malady, ATM has decided to travel to the seabed of the Pacific and slay this evil dragon once and for all.
After untold hardships, ATM has finally reached DRD's resting place. He
now braces for the arduous battle that lies ahead. DRD has a very
special tactic. His line of defense involves transforming the attack
power of the opponent using a series of calculations to minimize the
damage done to himself. Roughly speaking, DRD's line of defense consists
of defense gates. Each gate contains an operator and a
parameter . The operator is guaranteed to be one of OR
, XOR
, or
AND
, while the parameter is guaranteed to be a nonnegative integer. If
one's power before going through a defense gate is , then the power
after going through it is . Finally, the damage done to DRD
is equal to his opponent's initial striking power after it has
been through all defense gates.
Since ATM's skill is limited, the initial attack power of his strike can only be an integer between and (he many pick any number of to be his initial attack power), but the final attack power after it has been through the gates is not bounded by . To conserve energy, he will have to pick the optimal initial power with which to attack to maximize the damage done to DRD. Please help him calculate how much damage he can do to DRD with one strike.
Input Specification
The first line contains two integers and , indicating that DRD
uses defense gates and that ATM can pick any integer between and
as his initial striking power.
The next lines each describes a single defense gate. Each line
consists of a single string of characters representing , followed by
a space, followed by a nonnegative integer representing the
parameter number of that gate.
Output Specification
Output one line consisting of a single integer, representing the maximum possible damage that ATM could do to DRD in one strike.
Sample Input
3 10
AND 5
OR 6
XOR 7
Sample Output
1
Explanation
ATM can choose any one of the numbers as one of his initial
striking power.
If he chooses , then his final damage is calculated as follows:
4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1
Similarly, we can calculate to find out that initial striking powers of , , , , and will result in a damage of at the end. Initial striking powers of , , , , , and will all result in final damages of . Thus, ATM's maximum possible damage with one strike is .
Constraints
Test Case  ,  Guarantees  Notes 

1  , 
is one of OR , XOR , AND 

2 


3  
4  One gate with AND 0 will exist.  
5  All gates will have the same operator.  
6  
7 

All gates will have the same operator.  
8  
9  
10 
Hint
For this problem, competitors will have to first convert operands into binary. If two operands have different number of digits, then the shorter operand must be padded with leading 0's before carrying out the operation.
OR
is the bitwise OR operation. For two binary operands of equal
length, pairs of corresponding digits will yield a result of 1 if
either digit is 1, otherwise a result 0.
XOR
is the bitwise XOR operation. For two binary operands of equal
length, pairs of corresponding digits will yield a result of 1 if
the digits are different (distinct), otherwise a result 0.
AND
is the bitwise AND operation. For two binary operands of equal
length, pairs of corresponding digits will yield a result of 1 if
both digits are 1, otherwise a result 0.
For example, we can perform the OR
, XOR
, and AND
operations on
the decimal values 5 and 3, resulting in the following:
0101 (5 in base10)
OR 0011 (3 in base10)
= 0111 (7 in base10)
0101 (5 in base10)
XOR 0011 (3 in base10)
= 0110 (6 in base10)
0101 (5 in base10)
AND 0011 (3 in base10)
= 0001 (1 in base10)
Problem translated to English by .
Comments