Evaluate a binary operation string

A string alternates bits and operators, for example 1C0C1C1A0B1. Operators are A (AND), B (OR) and C (XOR). Evaluate it strictly from left to right and print the resulting bit.

Reported in: Accenture (Aug 2022) (memory-based)

Input

One line: the expression (odd length, starting and ending with a bit).

Output

0 or 1.

Constraints

1 ≤ length ≤ 10^5.

Example 1

Input:
1C0C1C1A0B1

Output:
1

Example 2

Input:
0

Output:
0

Hint: Keep a running value; read an operator and the next bit, apply it, repeat.

All coding practice