시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 72 41 37 64.912%

문제

가리송과 안드레송은 정산소에서 일하고 있고, 미래를 예측하고자 한다. 둘에게는 큰 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)

예제 입력 1

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

예제 출력 1

12
10
0
5
5
4
0
W3sicHJvYmxlbV9pZCI6IjExNzM1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHVjMGIwXHVjMThjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMDBcdWI5YWNcdWMxYTFcdWFjZmMgXHVjNTQ4XHViNGRjXHViODA4XHVjMWExXHVjNzQwIFx1YzgxNVx1YzBiMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWM3N2NcdWQ1NThcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWJiZjhcdWI3OThcdWI5N2MgXHVjNjA4XHVjZTIxXHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWI0NThcdWM1ZDBcdWFjOGNcdWIyOTQgXHVkMDcwIG4geCBuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMCZuYnNwO1x1YWMwMSBcdWJjMzBcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjICh4LHkpXHViMjk0Jm5ic3A7eCArIHkgXHViODVjIFx1Y2M0NFx1YzZjY1x1YzgzOFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyB4LCB5ICZsZTsgbikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmJmOFx1Yjc5OCBcdWM2MDhcdWNlMjFcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwXHVjNWQwIFx1YjQ1MFx1YWMwMFx1YzljMCBcdWQwYzBcdWM3ODVcdWM3NTggXHVjZmZjXHViOWFjXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mbGRxdW87UiZuYnNwO3ImcmRxdW87IFx1MzE2MSByXHVkNTg5XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFjMTJcdWI0ZTRcdWM3NDQgXHVkNTY5XHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIHJcdWQ1ODlcdWM3NDQgXHViYWE4XHViNDUwIDBcdWM3M2NcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mbGRxdW87QyZuYnNwO2MmcmRxdW87XHUzMTYxJm5ic3A7Y1x1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhYzEyXHViNGU0XHVjNzQ0IFx1ZDU2OVx1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBjXHVjNWY0XHVjNzQ0IFx1YmFhOFx1YjQ1MCAwXHVjNzNjXHViODVjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWNmZmNcdWI5YWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgblx1YWNmYyBcdWNmZmNcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4IHFcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4mbmJzcDssIDEgJmxlOyBxICZsZTsgMTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIHFcdWFjMWNcdWM3NTggXHVjOTA0XHViOWM4XHViMmU0Jm5ic3A7JmxkcXVvO1ImbmJzcDtyJnJkcXVvOyAoMSAmbGU7IHIgJmxlOyBuKSBcdWQ2MzlcdWM3NDAmbmJzcDsmbGRxdW87QyZuYnNwO2MmcmRxdW87ICgxICZsZTsgYyAmbGU7IG4pXHVjNzc4IFx1Y2ZmY1x1YjlhY1x1YmIzOFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPGJyIFwvPlxyXG4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgaVx1YmM4OFx1YzlmOCBcdWNmZmNcdWI5YWNcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoMSAmbGU7IGkmbmJzcDsmbGU7IHEpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE3MzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBZGp1c3RtZW50IE9mZmljZSIsImRlc2NyaXB0aW9uIjoiPHA+R2Fycmlzb24gYW5kIEFuZGVyc29uIGFyZSB3b3JraW5nIGluIGEgY29tcGFueSBuYW1lZCAmbGRxdW87QWRqdXN0bWVudCBPZmZpY2UmcmRxdW87LiBJbiBjb21wZXRpbmcgY29tcGFuaWVzIHdvcmtlcnMgY2hhbmdlIHRoZSByZWFsaXR5LCBpbiB0aGlzIGNvbXBhbnkgdGhleSB0cnkgdG8gcHJlZGljdCB0aGUgZnV0dXJlLjxcL3A+XHJcblxyXG48cD5UaGV5IGFyZSBnaXZlbiBhIGJpZyBzcXVhcmUgYm9hcmQgbiAmdGltZXM7IG4uIEluaXRpYWxseSBpbiBlYWNoIGNlbGwgKHgsIHkpIG9mIHRoaXMgYm9hcmQgdGhlIHZhbHVlIG9mIHggKyB5IGlzIHdyaXR0ZW4gKDEgJmxlOyB4LCB5ICZsZTsgbikuIFRoZXkga25vdyB0aGF0IGluIHRoZSBmdXR1cmUgdGhlcmUgd2lsbCBiZSB0d28gdHlwZXMgb2YgcXVlcmllcyBvbiB0aGUgYm9hcmQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JmxkcXVvOzxjb2RlPlI8XC9jb2RlPiByJnJkcXVvOyAmbWRhc2g7IHN1bSB1cCBhbGwgdmFsdWVzIGluIHJvdyByLCBwcmludCB0aGUgcmVzdWx0IGFuZCBzZXQgYWxsIHZhbHVlcyBpbiByb3cgciB0byB6ZXJvOzxcL2xpPlxyXG5cdDxsaT4mbGRxdW87PGNvZGU+QzxcL2NvZGU+IGMmcmRxdW87ICZtZGFzaDsgc3VtIHVwIGFsbCB2YWx1ZXMgaW4gY29sdW1uIGMsIHByaW50IHRoZSByZXN1bHQgYW5kIHNldCBhbGwgdmFsdWVzIGluIGNvbHVtbiBjIHRvIHplcm8uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhleSBoYXZlIHByZWRpY3RlZCB3aGF0IHF1ZXJpZXMgYW5kIHJlc3VsdHMgdGhlcmUgd2lsbCBiZS4gVGhleSBuZWVkIHRvIGVuc3VyZSB0aGF0IHRoZXkgaGF2ZSBjb3JyZWN0bHkgcHJlZGljdGVkIHRoZSByZXN1bHRzLiBIZWxwIHRoZW0gYnkgY29tcHV0aW5nIHRoZSByZXN1bHRzIG9mIHRoZSBxdWVyaWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBxICgxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPiZuYnNwOywgMSAmbGU7IHEgJmxlOyAxMDxzdXA+NTxcL3N1cD4mbmJzcDspICZtZGFzaDsgdGhlIHNpemUgb2YgdGhlIHNxdWFyZSBhbmQgdGhlIG51bWJlciBvZiBxdWVyaWVzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IHEgbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBxdWVyeS4gRWFjaCBxdWVyeSBpcyBlaXRoZXIgJmxkcXVvOzxjb2RlPlI8XC9jb2RlPiZuYnNwO3ImcmRxdW87ICgxICZsZTsgciAmbGU7IG4pIG9yICZsZHF1bzs8Y29kZT5DPFwvY29kZT4mbmJzcDtjJnJkcXVvOyAoMSAmbGU7IGMgJmxlOyBuKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZpbGUgc2hhbGwgY29udGFpbiBxIGxpbmVzLiBUaGUgaS10aCBsaW5lIHNoYWxsIGNvbnRhaW4gb25lIGludGVnZXIgJm1kYXNoOyB0aGUgcmVzdWx0IG9mIHRoZSBpLXRoIHF1ZXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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