편의점 단말의 배포 의존성

문제

한 편의점의 관리 단말에는 결제 보조, 진열 안내, 보관함 제어 등에 사용하는 소프트웨어 모듈 N개가 등록되어 있다. DevOps 담당자는 배포가 끝난 단말의 상태를 확인하고 실제로 실행할 수 있는 모듈을 판정하려고 한다. 모듈 번호는 1번부터 N번까지이며, 이 단말의 배포 도구는 번호를 이용해 의존 대상을 정한다. 1번 모듈은 다른 모듈에 의존하지 않는 기본 모듈이다. 2번 이상의 모듈 i는 i를 2로 나눈 몫을 번호로 갖는 모듈 하나에 직접 의존한다. 이를 i의 부모 모듈이라고 한다. 예를 들어 6번과 7번 모듈의 부모는 모두 3번 모듈이다. 부모 번호는 항상 자식 번호보다 작으므로 의존 관계에 순환은 없다. 직접 의존 대상 외의 추가 의존성은 주어지지 않는다. 각 모듈의 설치 버전은 한 자리 정수로 기록한다. 0은 해당 모듈이 설치되지 않았다는 뜻이며, 1부터 9까지는 설치된 버전 번호다. 이 문제에서는 버전 번호가 클수록 새로운 버전이고, 최소 요구 버전 이상의 모든 버전을 호환되는 것으로 취급한다. 설치되지 않은 모듈은 어떤 상황에서도 실행할 수 없다. 1번 모듈은 설치되어 있으면 실행할 수 있다. 다른 모듈은 자신이 설치되어 있고, 부모 모듈이 실행 가능하며, 부모의 설치 버전이 자신에게 지정된 최소 요구 버전 이상인 경우에만 실행할 수 있다. 세 조건을 모두 만족해야 한다. 자신의 설치 버전과 최소 요구 버전을 비교하는 것이 아니라 부모의 설치 버전과 비교한다는 점에 주의해야 한다. 부모가 설치되어 있어도 더 위의 의존성 때문에 실행할 수 없다면 자식 역시 실행할 수 없다. 입력에 주어진 상태를 검사하는 동안 설치나 버전 변경은 하지 않는다. 실행 가능한 모듈의 총수와 각 모듈의 실행 가능 여부를 번호 순서대로 구한다. 실행 가능한 모듈이 하나도 없으면 총수는 0이며 모든 판정 문자는 0이다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 V가 주어진다. 각 문자는 0부터 9까지의 숫자이며, i번째 숫자는 i번 모듈의 설치 버전이다. 0은 미설치를 뜻한다.
셋째 줄에 길이가 정확히 N인 문자열 R이 주어진다. 첫 문자는 항상 0이며 1번 모듈에는 사용하지 않는다. i ≥ 2인 위치의 문자는 1부터 9까지의 숫자로, i번 모듈이 부모 모듈에 요구하는 최소 버전이다.

출력

첫째 줄에 실행 가능한 모듈의 총수를 정수로 출력한다. 둘째 줄에 길이가 N인 문자열을 출력한다. i번 모듈이 실행 가능하면 i번째 문자를 1로, 실행 불가능하면 0으로 한다. 문자 사이에는 공백을 넣지 않는다.

7
3420516
0234132

5
1110101

1
0
0

0
0

3
519
061

2
101

출처: Devin.KR 자체 제작