시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2030 680 466 38.931%

문제

상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다.

보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다.

상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫자로 쉽게 구별할 수 있다.

각 영화의 위치를 기록하는 프로그램을 작성하시오. 상근이가 영화를 한 편 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야 한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.

영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다. 

출력

각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.

예제 입력 1

2
3 3
3 1 1
5 3
4 4 5

예제 출력 1

2 1 0
3 0 4
W3sicHJvYmxlbV9pZCI6IjM2NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MDFcdWQ2NTQgXHVjMjE4XHVjOWQxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjAxXHVkNjU0IERWRCBcdWMyMThcdWM5ZDFcdWFjMDBcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFkZjhcdWM3NTggRFZEIFx1Y2Y1Y1x1YjgwOVx1YzE1OFx1Yzc0NCBcdWMzMTNcdWM1NDQgXHViY2Y0XHVhZDAwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjZjRcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzYwMVx1ZDY1NFx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0LCBEVkRcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2MzZVx1Yzc0MCBcdWIyZTRcdWM3NGMgXHVjMzEzXHVjNTQ0XHViMTkzXHVjNzQwIFx1Y2Y1Y1x1YjgwOVx1YzE1OFx1Yzc3NCBcdWJiMzRcdWIxMDhcdWM5YzBcdWM5YzAgXHVjNTRhXHVhYzhjIFx1Yzg3MFx1YzJlY1x1YzJhNFx1YjdmZFx1YWM4YyBEVkRcdWI5N2MgXHViZTgwXHViMmU0LiBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViMmU0IFx1YmNmOCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBEVkRcdWFjMDAgXHViOWU0XHVjNmIwIFx1YjljZVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjYzNlXHViMjk0XHViMzcwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWIxMDhcdWJiMzQgXHVjNjI0XHViNzk4IFx1YWM3OFx1YjliMFx1YjJlNC4gXHVhYzAxIERWRFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQsIFx1Y2MzZVx1YzczY1x1YjgyNFx1YjI5NCBEVkRcdWM3NTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM2MDFcdWQ2NTRcdWM3NTggXHVhYzFjXHVjMjE4XHViOWNjIFx1YzU0Y1x1YmE3NCBcdWMyN2RcdWFjOGMgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM2MDFcdWQ2NTRcdWIyOTQgRFZEIFx1ZDQ1Y1x1YzljMFx1YzVkMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjIFx1YzI3ZFx1YWM4YyBcdWFkNmNcdWJjYzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhZTMwXHViODVkXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM2MDFcdWQ2NTRcdWI5N2MgXHVkNTVjIFx1ZDNiOCBcdWJjZmMgXHViNTRjXHViOWM4XHViMmU0IFx1YWRmOCBEVkRcdWM3NTggXHVjNzA0XHVjNWQwIFx1YmE4NyBcdWFjMWNcdWM3NTggRFZEXHVhYzAwIFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWMyMTggblx1YWNmYyBcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiwgbSAmbGU7IDEwMCwwMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM2MDFcdWQ2NTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM2MDFcdWQ2NTRcdWFjMDAgXHVjMzEzXHVjNWVjXHVjOWM0IFx1YzIxY1x1YzExY1x1YjI5NCAxXHViZDgwXHVkMTMwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzYwMVx1ZDY1NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBtXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMThcdWIyOTQgaVx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViY2ZjIFx1YjU0YyBcdWFkZjggXHVjNjAxXHVkNjU0XHVjNzU4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM1YzhcdWIzNTggRFZEXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjllNFx1YmM4OCBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViY2ZjIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWJjZjggXHVjNjAxXHVkNjU0IERWRFx1Yjk3YyBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW92aWUgY29sbGVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+TXIuIEsuIEkuIGhhcyBhIHZlcnkgYmlnIG1vdmllIGNvbGxlY3Rpb24uIEhlIGhhcyBvcmdhbml6ZWQgaGlzIGNvbGxlY3Rpb24gaW4gYSBiaWcgc3RhY2suIFdoZW5ldmVyIGhlIHdhbnRzIHRvIHdhdGNoIG9uZSBvZiB0aGUgbW92aWVzLCBoZSBsb2NhdGVzIHRoZSBtb3ZpZSBpbiB0aGlzIHN0YWNrIGFuZCByZW1vdmVzIGl0IGNhcmVmdWxseSwgZW5zdXJpbmcgdGhhdCB0aGUgc3RhY2sgZG9lc24mcnNxdW87dCBmYWxsIG92ZXIuIEFmdGVyIGhlIFx1ZmIwMW5pc2hlcyB3YXRjaGluZyB0aGUgbW92aWUsIGhlIHBsYWNlcyBpdCBhdCB0aGUgdG9wIG9mIHRoZSBzdGFjay48XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIHN0YWNrIG9mIG1vdmllcyBpcyBzbyBiaWcsIGhlIG5lZWRzIHRvIGtlZXAgdHJhY2sgb2YgdGhlIHBvc2l0aW9uIG9mIGVhY2ggbW92aWUuIEl0IGlzIHN1Zlx1ZmIwMWNpZW50IHRvIGtub3cgZm9yIGVhY2ggbW92aWUgaG93IG1hbnkgbW92aWVzIGFyZSBwbGFjZWQgYWJvdmUgaXQsIHNpbmNlLCB3aXRoIHRoaXMgaW5mb3JtYXRpb24sIGl0cyBwb3NpdGlvbiBpbiB0aGUgc3RhY2sgY2FuIGJlIGNhbGN1bGF0ZWQuIEVhY2ggbW92aWUgaXMgaWRlbnRpXHVmYjAxZWQgYnkgYSBudW1iZXIgcHJpbnRlZCBvbiB0aGUgbW92aWUgYm94LjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaW1wbGVtZW50IGEgcHJvZ3JhbSB3aGljaCB3aWxsIGtlZXAgdHJhY2sgb2YgdGhlIHBvc2l0aW9uIG9mIGVhY2ggbW92aWUuIEluIHBhcnRpY3VsYXIsIGVhY2ggdGltZSBNci4gSy4gSS4gcmVtb3ZlcyBhIG1vdmllIGJveCBmcm9tIHRoZSBzdGFjaywgeW91ciBwcm9ncmFtIHNob3VsZCBwcmludCB0aGUgbnVtYmVyIG9mIG1vdmllcyB0aGF0IHdlcmUgcGxhY2VkIGFib3ZlIGl0IGJlZm9yZSBpdCB3YXMgcmVtb3ZlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBuIGFuZCBtICgxICZsZTsgbiwgbSAmbGU7IDEwMCAwMDApOiB0aGUgbnVtYmVyIG9mIG1vdmllcyBpbiB0aGUgc3RhY2sgYW5kIHRoZSBudW1iZXIgb2YgbG9jYXRlIHJlcXVlc3RzLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIG0gaW50ZWdlcnMgYTxzdWI+MTxcL3N1Yj4sIC4uLiwgYTxzdWI+bTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IG4pIHJlcHJlc2VudGluZyB0aGUgaWRlbnRpZmljYXRpb24gbnVtYmVycyBvZiBtb3ZpZXMgdGhhdCBNci4gSy4gSS4gd2FudHMgdG8gd2F0Y2guPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIHNpbXBsaWNpdHksIGFzc3VtZSB0aGUgaW5pdGlhbCBzdGFjayBjb250YWlucyB0aGUgbW92aWVzIHdpdGggaWRlbnRpXHVmYjAxY2F0aW9uIG51bWJlcnMgMSwgMiwgLi4uLCBuIGluIGluY3JlYXNpbmcgb3JkZXIsIHdoZXJlIHRoZSBtb3ZpZSBib3ggd2l0aCBsYWJlbCAxIGlzIHRoZSB0b3AtbW9zdCBib3guPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIG0gaW50ZWdlcnMsIHdoZXJlIHRoZSBpLXRoIGludGVnZXIgZ2l2ZXMgdGhlIG51bWJlciBvZiBtb3ZpZSBib3hlcyBhYm92ZSB0aGUgYm94IHdpdGggbGFiZWwgYTxzdWI+aTxcL3N1Yj4sIGltbWVkaWF0ZWx5IGJlZm9yZSB0aGlzIGJveCBpcyByZW1vdmVkIGZyb20gdGhlIHN0YWNrLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGUgdGhhdCBhZnRlciBlYWNoIGxvY2F0ZSByZXF1ZXN0IGE8c3ViPmk8XC9zdWI+LCB0aGUgbW92aWUgYm94IHdpdGggbGFiZWwgYWkgaXMgcGxhY2VkIGF0IHRoZSB0b3Agb2YgdGhlIHN0YWNrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: doju