문제
크기가 n인 정수 배열 X가 있고, 0으로 초기화되어있다. 이 배열에 연산을 q번 적용하려고 한다.
배열에 적용할 수 있는 연산은 아래와 같이 두 종류가 있다.
덧셈: 모든 X[i]에 i를 더한다. (0 ≤ i < n)
뒤집기: 뒤집기 연산을 사용하려면 i ≤ j를 만족하는 i와 j가 필요하다. X[i]부터 X[j]까지 원소의 순서를 모두 뒤집는다. 즉, X[i], X[i+1], ..., X[j-1], X[j]의 순서가 뒤집힌다.
예를 들어, n = 6이고, 아래와 같이 연산을 다섯 번 적용한 경우를 살펴보자.
덧셈
덧셈
뒤집기 i = 0, j = 4
덧셈
뒤집기 i = 2, j = 5
가장 처음에 X는 [0, 0, 0, 0, 0, 0]이다. 각 연산을 사용한 결과는 아래와 같다.
[0, 1, 2, 3, 4, 5]
[0, 2, 4, 6, 8, 10]
[8, 6, 4, 2, 0, 10]
[8, 7, 6, 5, 4, 15]
[8, 7, 15, 4, 5, 6]
배열의 크기 n과 적용한 연산의 수 q, 그리고 적용한 연산이 주어졌을 때, 배열 X에 담겨있는 수를 구해보려고 한다.
크기가 m인 배열 Y가 주어졌을 때, 모든 연산을 적용한 후의 X[Y[i]] 값을 구해보자.
출력
총 m개의 줄에 X[Y[i]]값을 순서대로 한 줄에 하나씩 출력한다.
서브태스크 2 (6점)
1 ≤ n ≤ 1,000,000
0 ≤ q ≤ 10,000
1 ≤ m ≤ 5,000
예제 출력 3
복사
6
6
6
20
16
6
24
W3sicHJvYmxlbV9pZCI6IjE1OTMyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzMwXHVjNWY0XHVhY2ZjIFx1YzVmMFx1YzBiMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkMDZjXHVhZTMwXHVhYzAwIG5cdWM3NzggXHVjODE1XHVjMjE4IFx1YmMzMFx1YzVmNCBYXHVhYzAwIFx1Yzc4OFx1YWNlMCwgMFx1YzczY1x1Yjg1YyBcdWNkMDhcdWFlMzBcdWQ2NTRcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjMzBcdWM1ZjRcdWM1ZDAmbmJzcDtcdWM1ZjBcdWMwYjBcdWM3NDQgcVx1YmM4OCBcdWM4MDFcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMzBcdWM1ZjRcdWM1ZDAgXHVjODAxXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDUwIFx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMzY3XHVjMTQ4OiBcdWJhYThcdWI0ZTAgWFtpXVx1YzVkMCBpXHViOTdjIFx1YjM1NFx1ZDU1Y1x1YjJlNC4gKDAgJmxlOyBpICZsdDsgbik8XC9saT5cclxuXHQ8bGk+XHViNGE0XHVjOWQxXHVhZTMwOiBcdWI0YTRcdWM5ZDFcdWFlMzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjgyNFx1YmE3NCBpICZsZTsgalx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQmbmJzcDtpXHVjNjQwIGpcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBYW2ldXHViZDgwXHVkMTMwIFhbal1cdWFlNGNcdWM5YzAgXHVjNmQwXHVjMThjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHViNGE0XHVjOWQxXHViMjk0XHViMmU0LiBcdWM5ODksIFhbaV0sIFhbaSsxXSwgLi4uLCBYW2otMV0sIFhbal1cdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YjRhNFx1YzlkMVx1ZDc4Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBuID0gNlx1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHViMmU0XHVjMTJmIFx1YmM4OCBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWIzNjdcdWMxNDg8XC9saT5cclxuXHQ8bGk+XHViMzY3XHVjMTQ4PFwvbGk+XHJcblx0PGxpPlx1YjRhNFx1YzlkMVx1YWUzMCBpID0gMCwgaiA9IDQ8XC9saT5cclxuXHQ8bGk+XHViMzY3XHVjMTQ4PFwvbGk+XHJcblx0PGxpPlx1YjRhNFx1YzlkMVx1YWUzMCBpID0gMiwgaiA9IDU8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFhcdWIyOTQgWzAsIDAsIDAsIDAsIDAsIDBdXHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjYjBcdWFjZmNcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5bMCwgMSwgMiwgMywgNCwgNV08XC9saT5cclxuXHQ8bGk+WzAsIDIsIDQsIDYsIDgsIDEwXTxcL2xpPlxyXG5cdDxsaT5bOCwgNiwgNCwgMiwgMCwgMTBdPFwvbGk+XHJcblx0PGxpPls4LCA3LCA2LCA1LCA0LCAxNV08XC9saT5cclxuXHQ8bGk+WzgsIDcsIDE1LCA0LCA1LCA2XTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgblx1YWNmYyBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YzIxOCBxLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjODAxXHVjNmE5XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjMzBcdWM1ZjQgWFx1YzVkMCBcdWIyZjRcdWFjYThcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBtXHVjNzc4IFx1YmMzMFx1YzVmNCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjODAxXHVjNmE5XHVkNTVjIFx1ZDZjNFx1Yzc1OCBYW1lbaV1dIFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWM4MTVcdWMyMTggbiwgcSwgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwgMCAmbGU7IHEgJmxlOyAxMCwwMDAsIDEgJmxlOyBtICZsZTsgNSwwMDApLjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgcVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhY2IwXHVjYzk4IFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgJiMzOTthJiMzOTtcdWIwOTggJiMzOTtyJiMzOTtcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViMzAwLCAmIzM5O2EmIzM5O1x1YjI5NCBcdWIzNjdcdWMxNDggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgJiMzOTtyJiMzOTtcdWM3NDAgXHViNGE0XHVjOWQxXHVhZTMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICYjMzk7ciYjMzk7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWFjYmRcdWM2YjAsIFx1YWRmOCBcdWI0YTRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBcdWI0NTAgXHVjODE1XHVjMjE4IGksIGpcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IGkgJmxlOyBqICZsdDsgbik8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjQgWVx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgbVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBZW2ldICZsdDsgbik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgWFtZW2ldXVx1YWMxMlx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiwgcSwgbSAmbGU7IDIwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPjAgJmxlOyBxICZsZTsmbmJzcDsxMCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IG0gJmxlOyA1LDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM2MDhcdWMyZGNcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YzYwOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNTkzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9wZXJhdGlvbnMgb24gQXJyYXkgb2YgSW50ZWdlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ29pbmcgdG8gYXBwbHkgYSBmZXcgb3BlcmF0aW9ucyBvbiBhbiBhcnJheSBvZiBpbnRlZ2VycyBYLjxcL3A+XHJcblxyXG48cD5UaGUgYXJyYXkgWCBjb250YWlucyBuIGludGVnZXJzLCB3aGljaCBhcmUgaW5pdGlhbGl6ZWQgdG8gMCYjMzk7cyBhdCB0aGUgYmVnaW5uaW5nLiBZb3UgYXJlIGdvaW5nIHRvIGFwcGx5IGV4YWN0bHkgcSBvcGVyYXRpb25zIHRvIFguPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBwcmVjaXNlbHkgdHdvIGtpbmRzIG9mIG9wZXJhdGlvbnM6IGFkZGl0aW9uIGFuZCByZXZlcnNhbC4gV2hlbiB5b3UgYXBwbHkgdGhlIGFkZGl0aW9uIG9wZXJhdGlvbiB0byBYLCB5b3UgYXJlIGdvaW5nIHRvIGFkZCB2YWx1ZSBpIHRvIFhbaV0gKHNvIFhbaV0gYmVjb21lcyBpdHMgb2xkIHZhbHVlIHBsdXMgaSkgd2hlcmUgaSBpcyBiZXR3ZWVuIDAgYW5kIG4tMSwgaW5jbHVzaXZlICh3ZSB1c2UgMC1iYWVkIGluZGV4KS4gV2hlbiB5b3UgYXBwbHkgdGhlIHJldmVyc2FsIG9wZXJhdGlvbiB0byBYLCB5b3UgYXJlIGFsc28gZ2l2ZW4gdHdvIGluZGljZXMgKGksIGopIHdoZXJlIGkgJmxlOyBqIHN1Y2ggdGhhdCB5b3UgYXJlIGdvaW5nIHRvIHJldmVyc2UgdGhlIG9yZGVyIG9mIGVsZW1lbnRzIFhbaV0sIFhbaSsxXSwgLi4uLCBYW2otMV0sIFhbal0uPFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgc3VwcG9zZSB0aGF0IG4gPSA2LCBhbmQgeW91IGFwcGx5IHRoZSBmb2xsb3dpbmcgZml2ZSBvcGVyYXRpb25zIGluIG9yZGVyOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPmFkZGl0aW9uPFwvbGk+XHJcblx0PGxpPmFkZGl0aW9uPFwvbGk+XHJcblx0PGxpPnJldmVyc2FsIGk9MCwgaj00PFwvbGk+XHJcblx0PGxpPmFkZGl0aW9uPFwvbGk+XHJcblx0PGxpPnJldmVyc2FsIGk9Miwgaj01PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+SW4gdGhpcyBleGFtcGxlLCBYIGJlZ2lucyBhcyBbMCwgMCwgMCwgMCwgMCwgMF0uPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QWZ0ZXIgdGhlIGZpcnN0IG9wZXJhdGlvbiwgWCBiZWNvbWVzIFswLCAxLCAyLCAzLCA0LCA1XS48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgdGhlIHNlY29uZCBvcGVyYXRpb24sIFggYmVjb21lcyBbMCwgMiwgNCwgNiwgOCwgMTBdLjxcL2xpPlxyXG5cdDxsaT5BZnRlciB0aGUgdGhpcmQgb3BlcmF0aW9uLCBYIGJlY29tZXMgWzgsIDYsIDQsIDIsIDAsIDEwXS48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgdGhlIGZvdXJ0aCBvcGVyYXRpb24sIFggYmVjb21lcyBbOCwgNywgNiwgNSwgNCwgMTVdLjxcL2xpPlxyXG5cdDxsaT5BZnRlciB0aGUgZmlmdGggKGxhc3QpIG9wZXJhdGlvbiwgWCBiZWNvbWVzIFs4LCA3LCAxNSwgNCwgNSwgNl0uPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+WW91IGFyZSB3b25kZXJpbmcgYWJvdXQgdGhlIHZhbHVlcyBvZiBjZXJ0YWluIGVsZW1lbnRzIG9mIFgsIGFmdGVyIHlvdSBhcHBseSBhbGwgb2YgdGhlIHEgb3BlcmF0aW9ucy4gU3BlY2lmaWNhbGx5LCB5b3UgYXJlIGdpdmVuIGFuIGludGVnZXIgbSBhbmQgYW4gYXJyYXkgb2YgaW5kaWNlcyAoY29udGFpbmluZyBtIGVsZW1lbnRzKSAtLSBsZXQmIzM5O3MgY2FsbCB0aGlzIGFycmF5IG9mIGluZGljZXMgWS4gWW91IHdhbnQgdG8ga25vdyBYW1lbaV1dIGZvciBhbGwgaSBiZXR3ZWVuIDAgYW5kIG0tMSwgYWZ0ZXIgeW91IGZpbmlzaCBhcHBseWluZyB0aGUgb3BlcmF0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIHEsIGFuZCBtICgxICZsZTsmbmJzcDtuICZsZTsgMSwwMDAsMDAwLCAwICZsZTsgcSAmbGU7IDEwLDAwMCwgMSAmbGU7IG0gJmxlOyA1LDAwMCkuIFRoZSBmb2xsb3dpbmcgcSBsaW5lcyBkZXNjcmliZSBvcGVyYXRpb25zLCBvbmUgb3BlcmF0aW9uIHBlciBsaW5lLiBJbiBlYWNoIGxpbmUsIHRoZSBsaW5lIGNvbnRhaW5zIGVpdGhlciAmIzM5O2EmIzM5OyAob25lIGNoYXJhY3Rlcikgb3IgJiMzOTtyJiMzOTssIGksIGFuZCBqIHdoZXJlIGkgYW5kIGogYXJlIGluZGljZXMgb2YgWCAoaW50ZWdlcnMgYmV0d2VlbiAwIGFuZCBuLTEsIGluY2x1c2l2ZSkgYW5kIGkgJmxlOyZuYnNwO2ouIFRoZW4gdGhlIGxhc3QgbGluZSBjb250YWlucyBtIGludGVnZXJzICh0aGUgYXJyYXkgWSkgdGhhdCBhcmUgaW5kaWNlcyBvZiBYICh0aGVzZSBpbmRpY2VzIGFyZSBiZXR3ZWVuIDAgYW5kIG4tMSwgaW5jbHVzaXZlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3UgbXVzdCBvdXRwdXQgZXhhY3RseSBtIGxpbmVzIHdoZXJlIGVhY2ggbGluZSBjb250YWlucyB0aGUgdmFsdWUgWFtZW2ldXSBhZnRlciB5b3UgYXBwbHkgdGhlIHEgb3BlcmF0aW9ucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic3VidGFzazEiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuLCBxLCBtICZsZTsgMjAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAxLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IHEgJmxlOyZuYnNwOzEwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgbSAmbGU7IDUsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+VGhpcyBleGFtcGxlIHdhcyBkaXNjdXNzZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcbiJ9XQ==