The MacFax Donut Cafe is expanding its restaurants into Canada. To kickstart their operations, they decided to open up a restaurant on every intersection along Yonge Street. Yonge Street is one of the longest streets in the world, and is composed of intersections, beginning at Toronto's lakeshore with index and ending near Lake Simcoe with index . To simplify, each restaurant will be numbered the same as the intersection they are on. The company wants to celebrate their openings with a series of promotions, which they will announce on live television, each promotion consists of one of two events:
- Add free donut coupons to the stores in that order.
- Ask the audience to count the total number of coupons that have been placed in the stores modulo .
Since none of the other eager customers realize that they can use a computer program to find the answer, you try to code your program quickly before the game starts so you can win all the prizes.
For all subtasks:
|4||No additional constraints||55|
The first line will contain and .
lines of input follow in one of the following formats:
U l r kAdd free donut coupons to the stores as described above.
Q l rFind the total number of free donut coupons added to the stores modulo .
Q type query, print the answer modulo on a new line.
Sample Input 1
6 6 U 4 6 0 Q 4 5 U 1 4 1 Q 1 4 U 1 4 2 Q 4 4
Sample Output 1
2 11 21
Sample Explanation 1
The various stages of updates
Sample Input 2
10 11 U 1 10 5 Q 1 1 Q 2 2 Q 3 3 Q 4 4 Q 5 5 Q 6 6 Q 7 7 Q 8 8 Q 9 9 Q 10 10
Sample Output 2
1 32 243 1024 3125 7776 16807 32768 59049 100000