Server Time: Tue Nov 19, 2019 11:14 am
Welcome ( logout
1080 - Binary Simulation
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB

Given a binary number, we are about to do some operations on the number. Two types of operations can be here.

'I i j'    which means invert the bit from i to j (inclusive)

'Q i'    answer whether the ith bit is 0 or 1

The MSB (most significant bit) is the first bit (i.e. i=1). The binary number can contain leading zeroes.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a binary integer having length n (1 ≤ n ≤ 105). The next line will contain an integer q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form 'I i j' where i, j are integers and 1 ≤ i ≤ j ≤ n. Or the query will be in the form 'Q i' where i is an integer and 1 ≤ i ≤ n.

Output

For each case, print the case number in a single line. Then for each query 'Q i' you have to print 1 or 0 depending on the ith bit.

Sample Input

Output for Sample Input

2

0011001100

6

I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

1011110111

6

I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

Case 1:

0

1

1

0

Case 2:

0

0

0

1

Note

Dataset is huge, use faster i/o methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan