Consistent Binary Letters

In this problem, two friends have exchanged letters for m years. Every year, one letter is written as a binary string of fixed length n (i.e. a string of 0's and 1's). Due to fading with time, some characters in these letters have become unclear and are represented by a '?' (which can stand for either '0' or '1').

Assume that during a continuous period of years [l, r], the friend wrote exactly the same message S (a binary string of length n). A letter string A (with characters in {0,1,?}) is said to be consistent with a binary string B (only containing '0' and '1') if and only if for every position:

• If A has a '0' at that position, then B also has a '0'.
• If A has a '1' at that position, then B also has a '1'.
• If A has a '?' at that position, B can have either '0' or '1'.

You are given the initial m letters. Then, q queries follow. Each query is one of the following:

• Q l r: For the years l to r (inclusive), if the friend wrote the same message S then how many possible binary strings S are there such that every letter in the range [l, r] is consistent with S? The answer for a query is the product over all positions j from 1 to n of:
  • 1 if there is at least one revealed character (either '0' or '1') and they are all the same,
  • 2 if all characters are '?' in that position,
  • 0 if there is a conflict (i.e. both '0' and '1' appear in that position across the letters in the given interval).
• C i s: The letter for year i is modified to the new string s, which is also of length n and may contain characters '0', '1', or '?'.

For each query of type Q, output the number of possible binary strings S that are consistent with all letters in the specified range.

Note: All indices are 1-indexed.

inputFormat

The input begins with three integers n, m, and q, where n is the length of each letter, m is the number of initial letters, and q is the number of queries.

The next m lines each contain a string of length n consisting of characters '0', '1', and '?', representing each letter from year 1 to year m.

Each of the following q lines contains a query in one of the following two formats:

• Q l r - Query the number of possible messages if the friend wrote the same message in each year from l to r.
• C i s - Change the letter for year i to string s (of length n).

outputFormat

For each query of type Q, output the corresponding result on a new line.

sample

3 4 6
1?0
?10
11?
???
Q 1 2
Q 2 4
C 3 0?1
Q 1 4
C 4 110
Q 3 4

1
1
0
0