Logic Circuit (APCS 2024-01 Advanced)

Write a program that simulates a basic logic circuit. The circuit consists of input ports, logic gates, and output ports. You must propagate the signals, evaluate the gates, output every output-port value, and compute the circuit's maximum delay.

The circuit contains these components:

• Input ports: There are \(p\) input ports numbered \(1\) through \(p\). Each value is either \(0\) or \(1\).
• Logic gates: There are \(q\) gates numbered \(p+1\) through \(p+q\):
  • Type \(1\), AND: outputs \(1\) exactly when both inputs are \(1\).
  • Type \(2\), OR: outputs \(1\) when at least one input is \(1\).
  • Type \(3\), XOR: outputs \(1\) exactly when the two inputs differ.
  • Type \(4\), NOT: has one input and outputs its negation.
• Output ports: There are \(r\) output ports numbered \(p+q+1\) through \(p+q+r\). Each receives one signal.

Every wire is directed. The maximum delay is the largest number of logic gates on any path from an input port to an output port. The input and output ports themselves are not counted.

Input

The first line contains four integers \(p,q,r,m\): the numbers of input ports, logic gates, output ports, and wires.

The second line contains \(p\) integers \(v_1,v_2,\ldots,v_p\), the input-port values.

The third line contains \(q\) integers \(t_1,t_2,\ldots,t_q\), where \(t_i\) is the type of gate \(p+i\).

The next \(m\) lines each contain two integers \(a,b\), representing a directed wire from component \(a\) to component \(b\).

Constraints

• \(1\le p\le 10^3\)
• \(1\le q\le 5\times 10^4\)
• \(1\le r\le 10^3\)
• Every AND, OR, and XOR gate has exactly two input wires; every NOT gate has exactly one.
• Every output port has exactly one input wire.
• The output of every input port and logic gate connects to at least \(1\) and at most \(20\) other gates or output ports.
• The circuit has no directed cycle.
• The maximum delay does not exceed \(100\).

Output

Print the maximum delay on the first line.

On the second line, print the \(r\) output-port values in increasing port-number order, separated by spaces.

Scoring

There are \(20\) scored test cases. Each test case is worth \(5\) points.

Sample Input 1

4 5 4 13
1 0 1 0
1 2 3 4 1
1 5
2 5
2 6
3 6
3 7
4 7
4 8
5 10
6 9
6 11
7 9
8 13
9 12

Sample Output 1

2
0 1 1 1

Sample Input 2

5 6 4 15
1 1 0 1 0
2 1 3 4 1 3
1 6
2 7
7 13
7 6
3 7
3 8
4 8
5 9
8 10
9 10
10 14
10 11
9 11
6 12
11 15

Sample Output 2

3
1 0 1 0

Source

APCS January 2024, Programming Problem 3; ZeroJudge m933 Logic Circuit.