Informatica Online Judge

  논리회로 [1623 / 0657]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 43


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 최창호)]

Background

어려운 PS문제들로 지친 경곽이는 아두이노로 고급정보과학 숙제를 하면서 피로를 풀려고 한다.

고급정보과학 숙제는 아두이노로 논리회로를 만들고 그 회로를 조사하는 것이다.

회로는 m개의 입력 부분, n개의 출력부분, k개의 논리 게이트 그리고 l개의 도선으로 이루어져있다.

입력부분에서는 1 또는 0의 전기 신호가 입력된다. 논리 게이트는 각각 입력 부분, 연산 부분, 출력 부분으로 이루어져 있어 입력들을 받아서 연산한 결과를 출력한다.

논리 게이트들의 종류는 and, or, not으로 한정되어있고 and, or게이트는 2개의 입력부분과 출력부분이 있고 not게이트는 1개의 입력부분과 1개의 출력부분이 있다.

각각의 회로도의 입력부분과 논리 게이트의 출력부분은 여러 개의 논리게이트의 입력 부분 혹은 회로도의 출력 부분과 연결 될 수 있다.

(단, 모든 논리 게이트의 모든 입력부분은 연결되어 있고 회로도에 cycle이 없음이 보장되어있다.)


회로도를 다 완성한 경곽이는 갑자기 입력에 따라 출력값들이 어떻게 변하는지 알아보기가 귀찮아졌다. 경곽이를 도와 특정 입력이 주어졌을 때 회로도의 출력을 알아보자.

Input

첫번째 줄에 회로의 입력부분 개수 m, 출력부분의 개수 n, 논리게이트의 개수 k, 도선의 개수 l이 각각 주어진다.

이후 k개의 줄에 걸쳐 논리게이트의 종류가 숫자로 입력된다.

and 게이트일 경우 1, or 게이트일 경우 2, not 게이트일 경우 3이 입력된다. 그리고 l줄에 걸쳐 도선의 연결 상태가 4개의 숫자로 입력된다.

1번째 숫자와 3번째 숫자는 각각 연결된 입력부분과 출력부분의 종류를 나타낸다. (1일경우 회로도의 입력부분 또는 출력부분, 2일 경우 논리게이트) 2번째 숫자와 4번째 숫자는 연결된 부분이 몇번째 논리게이트 혹은 입력 또는 출력 부분인지를 나타낸다.

즉 1 2 2 5 는 2번째 회로도의 입력부분과 5번째 논리게이트의 입력부분이 연결된 것이다. 그리고 마자막 줄에 회로도의 입력부분의 전기신호인 0 또는 1이 m개 입력된다.

(m,n<=2000, k<=10000, l<=22000)

Output

회로도 출력부분의 전기신호인 0 또는 1을 순서대로 n개 출력한다.

IO Example

입력

2 1 1 3
1
1 1 2 1
1 2 2 1
2 1 1 1
1 1

출력

1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]