시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 29 13 10 52.632%

문제

가리송과 안드레송은 정산소에서 일하고 있고, 미래를 예측하고자 한다. 둘에게는 큰 n x n 정사각형이 주어진다. 처음에 각 배열의 원소 (x,y)는 x + y 로 채워져있다. (1 ≤ x, y ≤ n). 

미래 예측을 하는데에 두가지 타입의 쿼리가 들어온다.

  • “R r” ㅡ r행의 모든 값들을 합한 결과를 출력하고, r행을 모두 0으로 바꾼다.
  • “C c”ㅡ c열의 모든 값들을 합한 결과를 출력하고, c열을 모두 0으로 바꾼다.

쿼리 결과를 구하는 프로그램을 작성하시오.

입력

첫줄에는 배열의 크기 n과 쿼리의 개수 q가 입력된다. (1 ≤ n ≤ 106 , 1 ≤ q ≤ 105)

그 다음 q개의 줄마다 “R r” (1 ≤ r ≤ n) 혹은 “C c” (1 ≤ c ≤ n)인 쿼리문이 입력된다.
 

출력

q개의 줄에 걸쳐서 i번째 쿼리의 결과를 출력한다. (1 ≤ i ≤ q)

예제 입력

3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3

예제 출력

12
10
0
5
5
4
0

힌트

출처

ACM-ICPC > Regionals > Europe > Northeastern European Regional Contest > NEERC 2015 A번