시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0QVx1Yjk3YyAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI4NWMgKDFcdWFjZmMgTiBcdWMwYWNcdWM3NzRcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCAxXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNCkgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWI1NGMsIEJcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEJba10gPSAxIChcdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWNjOThcdWM3NGMga1x1YWMxYyBcdWM2ZDBcdWMxOGNcdWFjMDAgMVx1YWNmYyBLXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0Yyk8XC9wPlxyXG48cD4gJm5ic3A7ICZuYnNwOyAmbmJzcDsgJm5ic3A7MCAoXHVjNzA0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyZDAgXHViNTRjKTxcL3A+XHJcbjxwPiAmbmJzcDsgJm5ic3A7PFwvcD5cclxuPHA+XHJcblx0XHVjMjE4XHVjNWY0IEJcdWM2NDAgQVx1Yzc1OCBcdWM3N2NcdWJkODAgXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzIxOFx1YzVmNCBBXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBCXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0IEEgXHVjNmQwXHVjMThjXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMDAwLCAwICZsZTsgTSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0IEJcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNmQwXHVjMThjXHVhYzAwIFx1YjQ1MCBcdWMyMmJcdWM3OTAgWFx1YzY0MCBZXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKEFbWF0gPSBZKSBcdWM3NzQgXHVjODE1XHViY2Y0XHVjNWQwXHViMjk0IFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0ICYjMzk7LTEmIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzI2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCBBIGJlIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyBmcm9tIDEgdG8gTiBpbiByYW5kb20gb3JkZXIgKGV2ZXJ5IG51bWJlciBmcm9tIDEgdG8gTiBhcHBlYXJzIGV4YWN0bHkgb25jZSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGRlZmluZSB0aGUgc2VxdWVuY2UgQjombmJzcDs8XC9wPlxyXG5cclxuPHA+QltrXSA9IDEgLi4uIGlmIGFuZCBvbmx5IGlmIHRoZSBmaXJzdCBrIG51bWJlcnMgb2YgdGhlIHNlcXVlbmNlIEEgY29uc3Rpc3Qgb25seSBvZiBudW1iZXJzIDEgdG8gayBpbiByYW5kb20gb3JkZXIgKGV2ZXJ5IG51bWJlciBmcm9tIDEuLi5rIGFwcGVhcnMgZXhhY3RseSBvbmNlKSwmbmJzcDs8YnIgXC8+XHJcbiZuYnNwOyAmbmJzcDsgJm5ic3A7ICZuYnNwOzAgLi4uIG90aGVyd2lzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Uga25vdyB0aGUgc2VxdWVuY2UgQiBhbmQgc29tZSBvZiB0aGUgZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlIEEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoZSB3aWxsIHJlY29uc3RydWN0IHRoZSB3aG9sZSBzdHJpbmcgQS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgaW50ZWdlcnMgTiBhbmQgTSwgMSAmbGU7IE4gJmxlOyAxMDAwMDAsIDAgJmxlOyBNICZsZTsgTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2Vjb25kIGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZSBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD5OZXh0IE0gbGluZXMgY29uc2lzdCBvZiB0aGUgZGF0YSBhYm91dCB0aGUga25vd24gZWxlbWVudHMgb2Ygc2VxdWVuY2UgQSwgdHdvIGludGVnZXJzIFggYW5kIFkuIFRoYXQgbWVhbnMgdGhhdCB0aGUgWHRoIGVsZW1lbnQgb2Ygc2VxdWVuY2UgQSBpcyBZIChBW1hdPVkpLiBUaGlzIGluZm9ybWF0aW9uIHdpbGwgbm90IGJlIGNvbnRyYWRpY3RvcnkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHNob3VsZCBjb25zaXN0IG9mIHRoZSBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2UgQTsgdGhlIG51bWJlcnMgc2hvdWxkIGJlIHNlcGVyYXRlZCBieSB0aGUgc3BhY2UgY2hhcmFjdGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBubyBzb2xsdXRpb24sIHlvdXIgcHJvZ3JhbSBzaG91bGQgd3JpdGUgJiMzOTtub3QgZXhpc3QmIzM5OyBpbiB0aGUgb3V0cHV0IGZpbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSBzb2xsdXRpb24gZG9lc24mIzM5O3QgaGF2ZSB0byBiZSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d