시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 88 | 57 | 38 | 59.375% |
Adding two numbers several times is a time-consuming task, so you want to build a robot. The robot should have a string S = S1S2. . .SN of N characters on its memory that represents addition instructions. Each character of the string, Si, is either ‘A
’ or ‘B
’.
You want to be able to give Q commands to the robot, each command is either of the following types:
A
’ if it was previously ‘B
’, or changing it to ‘B
’ if it was previously ‘A
’.function f(L, R, A, B): FOR i from L to R if S[i] = 'A' A = A + B else B = A + B return (A, B)
You want to implement the robot’s expected behavior.
Input begins with a line containing two integers: N Q (1 ≤ N, Q ≤ 100 000) representing the number of characters in the robot’s memory and the number of commands, respectively. The next line contains a string S containing N characters (each either ‘A
’ or ‘B
’) representing the initial string in the robot’s memory. The next Q lines each contains a command of the following types.
There is at least one command of the second type.
For each command of the second type in the same order as input, output in a line two integers (separated by a single space), the value of A and B returned by f(L, R, A, B), respectively. As this output can be large, you need to modulo the output by 1 000 000 007.
5 3 ABAAA 2 1 5 1 1 1 3 5 2 2 5 0 1000000000
11 3 0 1000000000
For the first command, calling f(L, R, A, B) causes the following:
Therefore, f(L, R, A, B) will return (11, 3).
For the second command, string S will be updated to “ABBBB
”.
For the third command, the value of A will always be 0 and the value of B will always be 1 000 000 000. Therefore, f(L, R, A, B) will return (0, 1 000 000 000).