시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 4 4 33.333%

문제

A를 1부터 N까지 자연수가 임의의 순서로 (1과 N 사이의 모든 자연수는 1번씩 등장한다) 이루어진 수열이라고 하자.

이때, B를 다음과 같이 정의하자.

B[k] = 1 (수열 A의 처음 k개 원소가 1과 K사이의 숫자로만 이루어져 있을 때)

       0 (위의 경우가 아닐 때)

   

수열 B와 A의 일부 원소가 주어졌을 때, 수열 A를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 B의 크기 N과 알고 있는 수열 A 원소의 개수 M이 주어진다. (1 ≤ N ≤ 100000, 0 ≤ M ≤ N)

둘째 줄에는 수열 B의 원소가 주어진다.

다음 M개 줄에는 수열 A의 알고 있는 원소가 두 숫자 X와 Y로 주어진다. (A[X] = Y) 이 정보에는 모순이 존재하지 않는다.

출력

수열 A의 원소를 공백으로 구분하여 출력한다. 만약, 정답이 없다면 '-1'을 출력한다.

예제 입력 1

5 1
0 0 1 0 1
2 3

예제 출력 1

2 3 1 5 4
W3sicHJvYmxlbV9pZCI6IjMyNjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjRcdWI4NWMgXHVjMjE4XHVjNWY0IFx1YWQ2Y1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0QVx1Yjk3YyAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI4NWMgKDFcdWFjZmMgTiBcdWMwYWNcdWM3NzRcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCAxXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNCkgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YjU0YywgQlx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHJcblx0QltrXSA9IDEgKFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1Y2M5OFx1Yzc0YyBrXHVhYzFjIFx1YzZkMFx1YzE4Y1x1YWMwMCAxXHVhY2ZjIEtcdWMwYWNcdWM3NzRcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjKTxcL3A+XHJcbjxwPiAmbmJzcDsgJm5ic3A7ICZuYnNwOyAmbmJzcDswIChcdWM3MDRcdWM3NTggXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWI1NGMpPFwvcD5cclxuPHA+ICZuYnNwOyAmbmJzcDs8XC9wPlxyXG48cD5cclxuXHRcdWMyMThcdWM1ZjQgQlx1YzY0MCBBXHVjNzU4IFx1Yzc3Y1x1YmQ4MCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjE4XHVjNWY0IEFcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEJcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWFjZmMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM1ZjQgQSBcdWM2ZDBcdWMxOGNcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwMDAsIDAgJmxlOyBNICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgQlx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0IEFcdWM3NTggXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHViNDUwIFx1YzIyYlx1Yzc5MCBYXHVjNjQwIFlcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoQVtYXSA9IFkpIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWM1ZDBcdWIyOTQgXHViYWE4XHVjMjFjXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjMjE4XHVjNWY0IEFcdWM3NTggXHVjNmQwXHVjMThjXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQgJiMzOTstMSYjMzk7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjY1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IEEgYmUgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIGZyb20gMSB0byBOIGluIHJhbmRvbSBvcmRlciAoZXZlcnkgbnVtYmVyIGZyb20gMSB0byBOIGFwcGVhcnMgZXhhY3RseSBvbmNlKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgZGVmaW5lIHRoZSBzZXF1ZW5jZSBCOiZuYnNwOzxcL3A+XHJcblxyXG48cD5CW2tdID0gMSAuLi4gaWYgYW5kIG9ubHkgaWYgdGhlIGZpcnN0IGsgbnVtYmVycyBvZiB0aGUgc2VxdWVuY2UgQSBjb25zdGlzdCBvbmx5IG9mIG51bWJlcnMgMSB0byBrIGluIHJhbmRvbSBvcmRlciAoZXZlcnkgbnVtYmVyIGZyb20gMS4uLmsgYXBwZWFycyBleGFjdGx5IG9uY2UpLCZuYnNwOzxiciBcLz5cclxuJm5ic3A7ICZuYnNwOyAmbmJzcDsgJm5ic3A7MCAuLi4gb3RoZXJ3aXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBrbm93IHRoZSBzZXF1ZW5jZSBCIGFuZCBzb21lIG9mIHRoZSBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2UgQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhlIHdpbGwgcmVjb25zdHJ1Y3QgdGhlIHdob2xlIHN0cmluZyBBLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb25zaXN0cyBvZiBpbnRlZ2VycyBOIGFuZCBNLCAxICZsZTsgTiAmbGU7IDEwMDAwMCwgMCAmbGU7IE0gJmxlOyBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TZWNvbmQgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb25zaXN0cyBvZiB0aGUgZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlIEIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5leHQgTSBsaW5lcyBjb25zaXN0IG9mIHRoZSBkYXRhIGFib3V0IHRoZSBrbm93biBlbGVtZW50cyBvZiBzZXF1ZW5jZSBBLCB0d28gaW50ZWdlcnMgWCBhbmQgWS4gVGhhdCBtZWFucyB0aGF0IHRoZSBYdGggZWxlbWVudCBvZiBzZXF1ZW5jZSBBIGlzIFkgKEFbWF09WSkuIFRoaXMgaW5mb3JtYXRpb24gd2lsbCBub3QgYmUgY29udHJhZGljdG9yeS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgc2hvdWxkIGNvbnNpc3Qgb2YgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZSBBOyB0aGUgbnVtYmVycyBzaG91bGQgYmUgc2VwZXJhdGVkIGJ5IHRoZSBzcGFjZSBjaGFyYWN0ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIG5vIHNvbGx1dGlvbiwgeW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSAmIzM5O25vdCBleGlzdCYjMzk7IGluIHRoZSBvdXRwdXQgZmlsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHNvbGx1dGlvbiBkb2VzbiYjMzk7dCBoYXZlIHRvIGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=