Vivy is playing a game of bitwise telephone!
In this game, robots are sitting in a line. You give them the number to start. In an ideal world, the robots would simply transmit the number down the line. However, these robots are a bit mischievous.
Each robot has an integer and an associated operation, one of
XOR. When a robot receives a number, it will modify the number with its operation and . For instance, if the operation is
XOR and the number received is , the robot will pass on .
Vivy wants the number to appear at the end of this chain. However, to do so, she might have to bribe some robots. If she bribes a robot, she can change their value to whatever she likes.
Vivy wonders: what is the minimum number of robots she must bribe to get to appear at the end of the chain?
Subtask 1 [5%]
All operations are
Subtask 2 [30%]
Subtask 3 [10%]
Subtask 4 [20%]
Subtask 5 [15%]
Subtask 6 [20%]
No additional constraints.
The first line contains , , and .
The next lines contain a description of the robot. Each line first contains a character denoting the operation, either
XOR. After the operation is the integer .
Output the minimum number of robots you must bribe to get as the output. If you cannot produce , output
5 1 5 A 4 A 1 O 4 O 3 X 0
Bribing the fourth robot to change their number to will produce as output. Note that the output without bribing anyone would be .