Pearl Box and NAND Combination

You are given an initially empty pearl box. Each pearl is either white (represented by 0) or black (represented by 1). You can add pearls to both the left and right sides of the box. When a pearl is added to the left, it becomes the new leftmost pearl; when added to the right, it becomes the new rightmost pearl.

The combination of two colors A and B is defined as the NAND operation: $$A\operatorname{nand}B = \operatorname{not}(A \operatorname{and}B)$$ where the \(\operatorname{and}\) operation is the binary AND and \(\operatorname{not}\) is the binary NOT. In simpler terms, \(A \operatorname{nand} B\) equals 0 only when both A and B are 1; otherwise, it is 1.

The combination sum for a contiguous set of pearls is computed by combining them in order. If you are given positions x and y, then:

• If x ≤ y, define $$C(x,y) = A_x \operatorname{nand} A_{x+1} \operatorname{nand} \cdots \operatorname{nand} A_y,$$ where the combination is applied from left to right, i.e. first combine \(A_x\) and \(A_{x+1}\), then combine the result with \(A_{x+2}\), and so on.
• If x > y, define $$C(x,y) = A_x \operatorname{nand} A_{x-1} \operatorname{nand} \cdots \operatorname{nand} A_y,$$ where the combination is applied from right to left.
• When x = y, the combination sum is simply the value \(A_x\).

For example, given the sequence [1, 1, 0, 0]:

• The combination sum from position 2 to 4 (left-to-right) is $$ (1 \operatorname{nand} 0) \operatorname{nand} 0 = 1 \operatorname{nand} 0 = 1.$$
• The combination sum from position 3 to 1 (right-to-left) is $$ (0 \operatorname{nand} 1) \operatorname{nand} 1 = 1 \operatorname{nand} 1 = 0.$$
• The combination sum for a single position (e.g. from 2 to 2) is simply 1.

You will be given a sequence of operations. There are two types of operations:

• Insertion Operations:
  • L x: Insert a pearl with color x (0 or 1) to the left side of the box.
  • R x: Insert a pearl with color x (0 or 1) to the right side of the box.
• Query Operations:
  • QL p: Query the combination sum of pearls from the leftmost pearl to the p-th pearl from the left.
  • QR p: Query the combination sum of pearls from the rightmost pearl to the p-th pearl from the right.

For each query operation, output the result (either 0 or 1) on a new line.

inputFormat

The first line contains an integer Q, the number of operations.

Each of the next Q lines contains one operation in one of the following formats:

• L x: Insert a pearl with color x (0 or 1) at the left.
• R x: Insert a pearl with color x (0 or 1) at the right.
• QL p: Query the combination sum from the leftmost pearl to the p-th pearl (1-indexed) from the left.
• QR p: Query the combination sum from the rightmost pearl to the p-th pearl (1-indexed) from the right.

outputFormat

For each query operation, output a single line containing the resulting value (0 or 1).

sample

4
R 1
R 0
QL 2
QR 2

1
1

</p>