스위치 켜고 끄기

1번부터 차례대로 번호가 붙은 스위치들이 있다. 각 스위치는 켜져 있거나 꺼져 있다. 아래 표는 스위치 8개의 상태를 나타낸다. 1은 스위치가 켜진 상태, 0은 꺼진 상태를 뜻한다.

학생 몇 명을 뽑아 각 학생에게 1 이상 스위치 개수 이하인 자연수를 하나씩 준다. 학생은 자신의 성별과 받은 수에 따라 스위치의 상태를 바꾼다.

남학생은 스위치 번호가 자신이 받은 수의 배수인 스위치를 모두 바꾼다. 켜져 있던 스위치는 끄고, 꺼져 있던 스위치는 켠다. 그림 1과 같은 상태에서 남학생이 3을 받았다면, 그림 2처럼 3번과 6번 스위치의 상태를 바꾼다.

그림 1

여학생은 자신이 받은 수와 같은 번호의 스위치를 중심으로, 좌우 상태가 대칭이면서 가능한 한 많은 스위치를 포함하는 구간을 찾는다. 그리고 그 구간에 포함된 스위치를 모두 바꾼다. 이 구간의 스위치 개수는 항상 홀수이다.

예를 들어 그림 2에서 여학생이 3을 받았다면, 2번과 4번 스위치의 상태가 같고 1번과 5번 스위치의 상태도 같다. 따라서 그림 3처럼 1번부터 5번까지 모든 스위치의 상태를 바꾼다. 그림 2에서 여학생이 4를 받았다면, 3번과 5번 스위치의 상태가 다르므로 4번 스위치만 바꾼다.

그림 2

그림 3

스위치의 처음 상태와 각 학생의 성별, 받은 수가 주어진다. 학생들을 입력 순서대로 처리한 뒤, 모든 스위치의 마지막 상태를 출력하라.

첫째 줄에 스위치의 개수가 주어진다. 스위치의 개수는 100 이하인 양의 정수이다.

둘째 줄에 각 스위치의 상태가 순서대로 주어진다. 켜져 있으면 1, 꺼져 있으면 0으로 표시하며, 상태 사이에는 빈칸이 하나씩 있다.

셋째 줄에 학생 수가 주어진다. 학생 수는 100 이하인 양의 정수이다.

넷째 줄부터 마지막 줄까지 한 줄에 한 학생의 성별과 그 학생이 받은 수가 주어진다. 남학생은 1, 여학생은 2로 표시한다. 학생이 받은 수는 스위치 개수 이하인 양의 정수이다. 성별과 받은 수 사이에는 빈칸이 하나 있다.

1번 스위치부터 마지막 스위치까지 상태를 출력하되, 한 줄에 최대 20개씩 출력한다. 예를 들어 21번 스위치가 있다면 그 상태는 둘째 줄 맨 앞에 출력한다.

켜진 스위치는 1, 꺼진 스위치는 0으로 표시하고, 상태 사이에는 빈칸을 하나씩 둔다.