문제
길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 정수 $K$가 주어진다. 이때, 다음 쿼리를 $Q$개 수행하는 프로그램을 작성해 보자.
1 $s_i$ $e_i$: $A_{s_i}, A_{s_i+1}, \cdots, A_{e_i}$에 1ドル$을 더한다.2 $s_i$ $e_i$: $(A_{s_i}\bmod K) +(A_{s_i+1}\bmod K) +\cdots +(A_{e_i}\bmod K)$를 출력한다.
출력
$q_i = 2$인 쿼리에 대해 각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.
제한
- 1ドル\leq N\leq 2\times 10^6$
- 1ドル\leq K\leq 10^9$
- 1ドル\leq Q\leq 2 \times 10^4$
- $q_i \in \{1, 2 \}$
- 1ドル\leq s_i \leq e_i \leq N$
- 0ドル\leq A_i\leq 10^9$
- $q_i=2$인 쿼리가 하나 이상 주어짐
서브태스크
| 번호 | 배점 | 제한 | | 1 | 3 | $N, Q \leq 2500$
|
| 2 | 21 | $K = 2$
|
| 3 | 15 | $K \leq 20$
|
| 4 | 61 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMzNDk0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiS1NBIFx1YzIxOFx1YzVmNFx1YWNmYyBcdWNmZmNcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCAkTiRcdWM3NzggXHVjMjE4XHVjNWY0ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1YWNmYyBcdWM4MTVcdWMyMTggJEskXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWIyZTRcdWM3NGMgXHVjZmZjXHViOWFjXHViOTdjICRRJFx1YWMxYyBcdWMyMThcdWQ1ODlcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjE8XC9jb2RlPjxcL3NwYW4+IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj4kc19pJCAkZV9pJDxcL3NwYW4+OiAkQV97c19pfSwgQV97c19pKzF9LCBcXGNkb3RzLCBBX3tlX2l9JFx1YzVkMCAkMSRcdWM3NDQgXHViMzU0XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MjxcL2NvZGU+PFwvc3Bhbj4gPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPiRzX2kkICRlX2kkPFwvc3Bhbj46ICQoQV97c19pfVxcYm1vZCBLKSArKEFfe3NfaSsxfVxcYm1vZCBLKSArXFxjZG90cyArKEFfe2VfaX1cXGJtb2QgSykkXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJE4kLCAkSyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJEFfMSxBXzIsXFxjZG90cyxBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZmZjXHViOWFjXHViNGU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkcV9pJCwgJHNfaSQsICRlX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkcV9pJFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHVjZmZjXHViOWFjXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JHFfaSA9IDIkXHVjNzc4IFx1Y2ZmY1x1YjlhY1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWM3NTggXHViMmY1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZXEgTlxcbGVxIDJcXHRpbWVzIDEwXjYkPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgS1xcbGVxIDEwXjkkPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgUVxcbGVxIDIgXFx0aW1lcyAxMF40JDxcL2xpPlxyXG5cdDxsaT4kcV9pIFxcaW4gXFx7MSwgMiBcXH0kPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgc19pIFxcbGVxIGVfaSBcXGxlcSBOJDxcL2xpPlxyXG5cdDxsaT4kMFxcbGVxIEFfaVxcbGVxIDEwXjkkPFwvbGk+XHJcblx0PGxpPiRxX2k9MiRcdWM3NzggXHVjZmZjXHViOWFjXHVhYzAwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWQwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROLCBRIFxcbGVxIDI1MDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kSyA9IDIkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kSyBcXGxlcSAyMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMzNDk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1NBIFNlcXVlbmNlIGFuZCBRdWVyaWVzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgc2VxdWVuY2UmbmJzcDskQV8xLCBBXzIsIFxcY2RvdHMsJm5ic3A7QV9OJCwgYW5kIGEgcG9zaXRpdmUmbmJzcDtpbnRlZ2VyICRLJC4gV3JpdGUgYSBwcm9ncmFtIHRvIGV4ZWN1dGUgJFEkIHF1ZXJpZXMgb2YgdGhlIGZvbGxvd2luZy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MTxcL2NvZGU+PFwvc3Bhbj4mbmJzcDs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+JHNfaSQgJGVfaSQ8XC9zcGFuPjogQWRkICQxJCB0byBlYWNoIG9mICRBX3tzX2l9LCZuYnNwO0Ffe3NfaSsxfSwgXFxjZG90cywgQV97ZV9pfSQuPFwvbGk+XHJcblx0PGxpPjxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4yPFwvY29kZT48XC9zcGFuPiA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+JHNfaSQgJGVfaSQ8XC9zcGFuPjogUHJpbnQgdGhlIHZhbHVlIG9mICQoQV97c19pfVxcYm1vZCBLKSArKEFfe3NfaSsxfVxcYm1vZCBLKSArXFxjZG90cyArKEFfe2VfaX1cXGJtb2QgSykkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICROJCBhbmQgJEskLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJE4kJm5ic3A7c3BhY2Utc2VwYXJhdGVkIGludGVnZXJzJm5ic3A7JEFfMSxBXzIsXFxjZG90cyxBX04kLjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBhbiZuYnNwO2ludGVnZXIgJFEkLjxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIGxpbmUgb2YgdGhlIGZvbGxvd2luZyAkUSQgbGluZXMgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRxX2kkLCAkc19pJCwgYW5kICRlX2kkLiZuYnNwOyRxX2kkIGRlbm90ZXMgdGhlIHR5cGUgb2YgdGhlICRpJC10aCBxdWVyeS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSBvZiB0aGUgdHlwZSAkcV9pPTIkLCBwcmludCB0aGUgYW5zd2VyIG9mIHRoZSBxdWVyeSBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGVxIE5cXGxlcSAyXFx0aW1lcyAxMF42JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIEtcXGxlcSAxMF45JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIFFcXGxlcSAyIFxcdGltZXMgMTBeNCQ8XC9saT5cclxuXHQ8bGk+JHFfaSBcXGluIFxcezEsIDIgXFx9JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIHNfaSBcXGxlcSBlX2kmbmJzcDtcXGxlcSBOJDxcL2xpPlxyXG5cdDxsaT4kMFxcbGVxIEFfaVxcbGVxIDEwXjkkPFwvbGk+XHJcblx0PGxpPlRoZXJlIGlzIGF0IGxlYXN0IG9uZSBxdWVyeSB3aXRoIHR5cGUgJHFfaT0yJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiwgUSBcXGxlcSAyNTAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JEsgPSAyJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JEsgXFxsZXEgMjAkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzPFwvcD5cclxuIn1d