Vivy is playing a game of bitwise telephone!

In this game, ~N~ robots are sitting in a line. You give them the number ~S~ 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 ~a_i~ 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 ~a_i~. For instance, if the operation is XOR and the number received is ~x~, the robot will pass on ~x \oplus a_i~.

Vivy wants the number ~T~ 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 ~a_i~ to whatever she likes.

Vivy wonders: what is the minimum number of robots she must bribe to get ~T~ to appear at the end of the chain?

Constraints

~1 \le N \le 10^6~

~0 \le S, T, a_i < 2^{30}~

Subtask 1 [5%]

All operations are XOR.

Subtask 2 [30%]

~S = 0~

~T = 2^{30}-1~

Subtask 3 [10%]

~1 \le N \le 100~

~0 \le S, T, a_i < 2^{10}~

Subtask 4 [20%]

~1 \le N \le 100~

~0 \le S, T, a_i < 2^{17}~

Subtask 5 [15%]

~1 \le N \le 5 \times 10^3~

Subtask 6 [20%]

No additional constraints.

Input Specification

The first line contains ~N~, ~S~, and ~T~.

The next ~N~ 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 ~a_i~.

Output Specification

Output the minimum number of robots you must bribe to get ~T~ as the output. If you cannot produce ~T~, 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 ~1~ will produce ~T~ as output. Note that the output without bribing anyone would be ~7~.