Students of Computer Science department at NIT Durgapur were becoming extremely bored and frustrated due to too many classes ( weird but we had many classes ). As semesters were approaching, students were preparing hard to get good grades. Everyone was nervous about the Algorithms exam which is going to be held 2 days later. To add to their discomfort, one question came in the exam which took many one by surprise. The question was simple but everyone was told to optimize code as much as possible.

Now its your turn, and the question states that there is initially an array of N non-negative numbers (1-based indexing) and based on that array we have to run Q queries. Now we can do three things in each query. We have to sometimes calculate sum of product of all subsets of a number within a range, sometimes to calculate sum of bitwise AND of all subsets of a number, sometimes to update an element of an array. All the calculations are to be performed modulus (10⁹+7). If we have to do sum of products then the query is given 'M', if bitwise AND then 'A' else if update then 'U'. For more details, see Explanation section .

Note: bitwise AND operator is defined as & in C, C++ and in most of the languages. For other programming languages see your language documentation.

Input

First line contains N, which denotes the number of elements in an array. Next line contains N integers denoting the number of integers in the array. Then Q denoting the number of queries and after that each line consists of 3 integers. If it is 'M' then we have to do product, if 'A' then bitwise AND and if 'U' then update. If it is 'M' or 'A' then it is followed by i and j which is the range of that array. If 'U' then we have the position and the value to be updated at that position.

Output

Corresponding to each query we have an output only to query of 'M' and 'A'. For update you don't have to print anything.

Constraints

1 ≤ N ≤ 10⁵
1 ≤ A[i] ≤ 10⁵
1 ≤ Q ≤ 10⁵
1 ≤ i ≤ j ≤ 10⁵
The element to be updated is of maximum value of 10⁵.

Example

Input:
3
1 2 3
5
M 1 3
A 1 3
U 2 5
M 1 3
A 1 3

Output:
23
9
47
13

Explanation

For 1st query, we do 1 + 2 + 3 + 1*2 + 1*3 + 2*3 + 1*2*3 = 23

For 2nd query, it is 1 + 2 + 3 + 1&2 + 1&3 + 2&3 + 1&2&3 = 9

For 3rd query, it is update so array becomes 1 5 3

For 4th query, it is 1 + 5 + 3 + 1*5 + 1*3 + 3*5 + 1*3*5 = 47

For 5th query, it is 1 + 5 + 3 + 1&5 + 1&3 + 3&5 + 1&3&5 = 13