시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 41 14 9 30.000%

문제

학생들은 몸이 약해지지 않도록 무술을 연마한다. 그 중에 대표적인 것으로 활쏘기 연습을 꼽을 수 있다. 한 가지 특이한 점은, 이 활쏘기 연습에 특별한 과녁이 동원되지 않는다는 것이다. 대신, 여러분의 동료가 과녁이 된다!

학생들은 두 줄로 길게 늘어서 있다. 그리고 각 학생들은 반대편 줄 쪽에 서 있는 친구 중 한 명을 바라보고 있다. 다소 충격적일 수는 있지만, 활시위를 당길 준비를 하고 있는 것이다.

그러나 연습은 어디까지나 연습일 뿐이므로, 중간에 다치는 사람이 있어서는 안 된다. 따라서 학생들 중 몇몇은 활 대신 방패를 들어야만 한다. 나머지 학생들을 예정대로 활을 든다. 활쏘기 연습을 위해서.

두 줄로 늘어선 학생들이, 각각 반대편의 어떤 학생을 바라보고 있는지 주어질 때, 각 학생들이 활을 들어야 하는지 혹은 방패를 들어야 하는지를 알아내는 프로그램을 작성하시오.

단, 쓸데없이 방패를 드는 학생이 있어서는 안 된다. 즉 방패를 드는 학생은, 반드시 활을 든 반대편의 학생 중 한 명으로부터 조준당하고 있어야 한다.

입력

첫째 줄에 두 자연수 m, n이 주어진다. (1<=m, n<=50,000) 한쪽 줄에 m명의 학생이, 반대편 줄에 n명의 학생이 서 있다는 의미이다.

학생들이 늘어선 두 개의 줄을 각각 A, B라고 하자. A줄에 늘어선 m 명의 학생은 1∼m까지 차례로 번호가 붙어 있고, B 줄에 늘어선 n 명의 학생은 n명의 학생은 1∼n까지 차례로 번호가 붙어 있다.

두 번째 줄에는 m개의 수가 주어지는데, k번째 수는 A줄의 k번 학생이 바라보고 있는 B줄의 학생 번호이다. 세 번째 줄에는 마찬가지의 방식으로, B줄의 각 학생이 바라보고 있는 A줄의 학생 번호가 주어진다.

출력

첫째 줄에는 A줄의 각 학생들이 활을 들어야 하는지, 방패를 들어야 하는지를 하나의 문자열로 출력한다. k번째 문자가 1이면 k번 학생이 활을 들어야 한다는 의미이고, 0이면 방패를 들어야 한다는 의미이다. 둘째 줄에는 마찬가지의 방식으로, B줄의 각 학생들이 활을 들어야 하는지 방패를 들어야 하는지를 출력한다.

예제 입력

4 5
3 5 2 5
4 4 4 1 3

예제 출력

0110
10110

힌트