My Bad

논리 회로는 여러 게이트를 거쳐 입력을 출력으로 변환하며, 회로에는 피드백 루프가 없다. 입력과 출력은 순서가 있는 논리값의 집합이고, 여기서는 1과 0으로 나타낸다. 이 문제에서 다루는 회로는 and 게이트(두 입력이 모두 1일 때만 1을 출력), or 게이트(두 입력 중 하나 이상이 1이면 1을 출력), exclusive or(xor) 게이트(두 입력 중 정확히 하나만 1일 때 1을 출력), not 게이트(하나뿐인 입력의 여집합을 출력)로 구성된다. 아래 그림은 두 회로를 보여 준다.

그림 1: 게이트가 2개인 회로	그림 2: 게이트가 4개인 회로

아쉽게도 실제 게이트는 때때로 고장 난다. 고장은 여러 방식으로 일어날 수 있지만, 이 문제에서는 게이트가 다음 세 가지 중 하나로 고장 나는 경우만 다룬다. 1) 올바른 출력을 항상 반전한다, 2) 항상 0을 출력한다, 3) 항상 1을 출력한다. 이 문제의 회로에서는 기껏해야 게이트 하나만 고장 난다.

회로와, 그 회로의 입력 및 출력에 대한 여러 관측값이 주어졌을 때 회로가 올바르게 동작하는지 고장 났는지 판별하는 프로그램을 작성해야 한다. 입력값 중 적어도 하나가 잘못된 출력을 낸다면, 고장 난 게이트 하나와 그 고장 방식을 알아내야 한다. 항상 알아낼 수 있는 것은 아니다.

입력은 여러 테스트 케이스로 이루어지며, 각 테스트 케이스는 회로와 그 입력 및 출력 설명을 담는다. 각 테스트 케이스는 다음 부분을 순서대로 가진다.

1. 회로의 입력 수(N ≤ 8), 게이트 수(G ≤ 19), 출력 수(U ≤ 19)를 나타내는 양의 정수 세 개가 있는 한 줄.
2. 게이트마다 한 줄씩 주어지는 입력. 첫 줄은 게이트 g1을 설명한다. 게이트가 여러 개라면 다음 줄은 게이트 g2를 설명하고, 이런 식으로 이어진다. 각 줄에는 게이트 종류(a = and, n = not, o = or, x = exclusive or)와 게이트의 입력이 무엇인지가 들어 있다. 게이트 입력은 회로 입력(i1, i2, …)이나 다른 게이트의 출력(g1, g2, …)에서 온다.
3. U개의 출력 u1, u2, …에 연결된 게이트 번호가 있는 한 줄. 예를 들어 출력이 세 개이고 u1이 g5에서, u2가 g1에서, u3가 g4에서 온다면 이 줄은 5 1 4가 된다.
4. 회로 동작의 관측 횟수(B)를 나타내는 정수가 있는 한 줄.
5. 마지막으로 B개의 줄. 각 줄에는 관측된 입력값 N개(1과 0)와 그에 대응하는 관측된 출력값 U개가 들어 있다. 두 관측의 입력값이 같은 경우는 없다.

입력의 어느 줄에서든 연속한 값들은 공백 하나로 구분된다. 입력은 0 세 개가 있는 줄로 끝난다.

입력에 있는 각 회로마다 케이스 번호(1부터 시작)를 출력하고, 그 뒤에 콜론과 공백을 출력한 다음 회로 분석 결과를 출력한다. 분석 결과는 다음 중 하나이며 # 자리에는 알맞은 게이트 번호가 들어간다.

No faults detected
Gate # is failing; output inverted
Gate # is failing; output stuck at 0
Gate # is failing; output stuck at 1
Unable to totally classify the failure

그림 1과 그림 2의 회로는 첫 번째와 마지막 샘플 테스트 케이스에 사용된다.