## 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 .