DMOPC '21 Contest 10 P4 - Bitwise Telephone

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 AND, OR, or 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?

Constraints

All operations are XOR.

Input Specification

The first line contains , , and .

The next lines contain a description of the robot. Each line first contains a character denoting the operation, either A denoting AND, O denoting OR, or X denoting XOR. After the operation is the integer .

Output Specification

Output the minimum number of robots you must bribe to get as the output. If you cannot produce , output -1.

Sample Input

5 1 5
A 4
A 1
O 4
O 3
X 0

Sample Output

1

Explanation

Bribing the fourth robot to change their number to will produce as output. Note that the output without bribing anyone would be .