톱니바퀴 (2)

톱니가 8개씩 달린 톱니바퀴 T개가 아래 그림처럼 일렬로 놓여 있다. 톱니는 N극과 S극 중 하나를 나타낸다. 톱니바퀴에는 왼쪽부터 번호가 매겨져 있어서, 가장 왼쪽이 1번, 그 오른쪽이 2번, 가장 오른쪽이 T번이다. 아래 그림은 T가 4인 경우다.

이 톱니바퀴를 모두 K번 회전시킨다. 한 번의 회전은 톱니 한 칸만큼이고, 방향은 시계 방향과 반시계 방향 두 가지다. 회전하는 모습은 아래 그림과 같다.

회전시키려면 회전시킬 톱니바퀴와 방향을 정해야 한다. 톱니바퀴가 회전할 때 맞닿은 톱니의 극에 따라 옆 톱니바퀴가 같이 돌기도 하고 돌지 않기도 한다. 톱니바퀴 A가 회전할 때 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르면, B는 A가 회전한 방향과 반대 방향으로 회전한다. 맞닿은 극이 같으면 B는 회전하지 않고, 회전하지 않은 톱니바퀴는 그 너머로 회전을 전달하지 않는다. 서로 맞닿는 톱니는 왼쪽 톱니바퀴의 3번째 톱니(3시 방향)와 오른쪽 톱니바퀴의 7번째 톱니(9시 방향)다. 예를 들어 아래와 같은 경우를 살펴보자.

두 톱니바퀴가 맞닿은 부분은 초록색 점선으로 묶여 있는 부분이다. 여기서 3번 톱니바퀴를 반시계 방향으로 회전시키면 4번 톱니바퀴는 시계 방향으로 회전한다. 2번 톱니바퀴는 맞닿은 부분이 둘 다 S극이라 회전하지 않고, 2번이 회전하지 않았으므로 1번도 회전하지 않는다. 따라서 아래 그림과 같은 모양이 된다.

이 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면 2번 톱니바퀴가 반시계 방향으로 회전하고, 2번이 회전하므로 3번도 함께 시계 방향으로 회전한다. 4번은 3번과 맞닿은 극이 같아서 회전하지 않는다. 따라서 아래와 같은 상태가 된다.

톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다.

둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 공백 없이 붙어 있는 8개의 숫자이고, 12시 방향부터 시계 방향 순서다. N극은 0, S극은 1로 나타낸다.

다음 줄에는 회전 횟수 K (1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어지고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1이면 시계 방향, -1이면 반시계 방향이다.

총 K번 회전시킨 이후에 12시 방향이 S극인 톱니바퀴의 개수를 출력한다.