시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB54181428.571%

문제

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

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

  • B[k] = 1 (수열 A의 처음 k개 원소가 1과 K사이의 숫자로만 이루어져 있을 때)
  • B[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

예제 입력 2

7 2
0 0 0 1 0 0 1
1 2
5 6

예제 출력 2

2 4 3 1 6 7 5

예제 입력 3

8 3
0 0 0 1 0 0 1 1
1 2
5 6
2 7

예제 출력 3

-1
W3sicHJvYmxlbV9pZCI6IjMyNjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjRcdWI4NWMgXHVjMjE4XHVjNWY0IFx1YWQ2Y1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+QVx1Yjk3YyAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI4NWMgKDFcdWFjZmMgTiBcdWMwYWNcdWM3NzRcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCAxXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNCkgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YywgQlx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5CW2tdID0gMSAoXHVjMjE4XHVjNWY0IEFcdWM3NTggXHVjYzk4XHVjNzRjIGtcdWFjMWMgXHVjNmQwXHVjMThjXHVhYzAwIDFcdWFjZmMgS1x1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMpPFwvbGk+XHJcblx0PGxpPkJba10gPSAwIChcdWM3MDRcdWM3NTggXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWI1NGMpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IEJcdWM2NDAgQVx1Yzc1OCBcdWM3N2NcdWJkODAgXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzIxOFx1YzVmNCBBXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBCXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0IEEgXHVjNmQwXHVjMThjXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMDAwLCAwICZsZTsgTSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0IEJcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNmQwXHVjMThjXHVhYzAwIFx1YjQ1MCBcdWMyMmJcdWM3OTAgWFx1YzY0MCBZXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKEFbWF0gPSBZKSBcdWM3NzQgXHVjODE1XHViY2Y0XHVjNWQwXHViMjk0IFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0ICYjMzk7LTEmIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzI2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCBBIGJlIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyBmcm9tIDEgdG8gTiBpbiByYW5kb20gb3JkZXIgKGV2ZXJ5IG51bWJlciBmcm9tIDEgdG8gTiBhcHBlYXJzIGV4YWN0bHkgb25jZSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGRlZmluZSB0aGUgc2VxdWVuY2UgQjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5CW2tdID0gMSAuLi4gaWYgYW5kIG9ubHkgaWYgdGhlIGZpcnN0IGsgbnVtYmVycyBvZiB0aGUgc2VxdWVuY2UgQSBjb25zdGlzdCBvbmx5IG9mIG51bWJlcnMgMSB0byBrIGluIHJhbmRvbSBvcmRlciAoZXZlcnkgbnVtYmVyIGZyb20gMS4uLmsgYXBwZWFycyBleGFjdGx5IG9uY2UpLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT5CW2tdID0gMCAuLi4gb3RoZXJ3aXNlLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldlIGtub3cgdGhlIHNlcXVlbmNlIEIgYW5kIHNvbWUgb2YgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZSBBLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGUgd2lsbCByZWNvbnN0cnVjdCB0aGUgd2hvbGUgc3RyaW5nIEEuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnNpc3RzIG9mIGludGVnZXJzIE4gYW5kIE0sIDEgJmxlOyBOICZsZTsgMTAwMDAwLCAwICZsZTsgTSAmbGU7IE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNlY29uZCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnNpc3RzIG9mIHRoZSBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2UgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TmV4dCBNIGxpbmVzIGNvbnNpc3Qgb2YgdGhlIGRhdGEgYWJvdXQgdGhlIGtub3duIGVsZW1lbnRzIG9mIHNlcXVlbmNlIEEsIHR3byBpbnRlZ2VycyBYIGFuZCBZLiBUaGF0IG1lYW5zIHRoYXQgdGhlIFh0aCBlbGVtZW50IG9mIHNlcXVlbmNlIEEgaXMgWSAoQVtYXT1ZKS4gVGhpcyBpbmZvcm1hdGlvbiB3aWxsIG5vdCBiZSBjb250cmFkaWN0b3J5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgZmlsZSBzaG91bGQgY29uc2lzdCBvZiB0aGUgZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlIEE7IHRoZSBudW1iZXJzIHNob3VsZCBiZSBzZXBlcmF0ZWQgYnkgdGhlIHNwYWNlIGNoYXJhY3Rlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgaXMgbm8gc29sbHV0aW9uLCB5b3VyIHByb2dyYW0gc2hvdWxkIHdyaXRlICYjMzk7LTEmIzM5OyBpbiB0aGUgb3V0cHV0IGZpbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSBzb2xsdXRpb24gZG9lc24mIzM5O3QgaGF2ZSB0byBiZSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==