Professor W teaches a "Digital Logic" course in the Computer Science Department at T University, focusing on how to design logic circuits. One day, Professor W assigned an experiment: design and implement a logic decoding circuit with 4 inputs and 4 outputs. Designing such a circuit is not difficult in itself, but the professor imposed the following requirements:
- Only 2-input, 1-output gate circuits are allowed as components for the circuit, and the types and quantities of available gate circuits are given.
- Use the minimum number of gate circuits.
These two requirements stumped the students, so Student Q found you, who are participating in the CTSC (China Team Selection Contest), and hopes you can help write a program to automatically find a connection method that meets the requirements.
In digital logic, all signals can be considered to have only two values: "high level" and "low level," represented by "1" and "0," respectively.
The characteristics of a gate circuit component are uniquely defined by its input/output function table, which is a table showing the relationship between input signal levels and output signal levels. For example, the symbol and function table for an "AND gate" are shown below:
Figure 1. Symbol and function table for an AND gate
In the figure above, if both inputs X and Y of the "AND gate" are high level "1", the output S is also high level "1"; otherwise, the output S is low level "0".
Assume that the gate circuits provided for this experiment have input symmetry, meaning that swapping the signals at the two inputs does not change the output. However, if an input of a gate circuit is left floating (i.e., no input signal is applied), the output is meaningless.
During the circuit connection process, the output of one gate circuit can send signals to the inputs of multiple other components; however, one input of a gate circuit can only receive a signal from one output. As shown in the figure below:
In addition, it is stipulated that signals must be transmitted in one direction, meaning the output of a gate circuit cannot directly or indirectly return to the input of the same gate circuit through other gate circuits. The figure below shows two disallowed connection methods:
The decoding circuit you are required to design is a logic circuit with four inputs and four outputs. The input and output relationship of this decoding circuit is given by a function table, which specifies the state of the four outputs for every input combination. Obviously, there are $2^4 = 16$ input combinations. For example, a simple 2-input, 2-output decoding circuit constructed from the aforementioned "AND gate" is shown below (where A1, A2 are inputs, and Y1, Y2 are outputs):
Input
The input file is digilog.in.
The first line contains a positive integer $n$ ($n \le 5$), representing the number of component types, followed by $n$ consecutive lines, each describing one type of component. For each positive integer $k$ ($1 \le k \le n$):
The $(k+1)$-th line of the file contains four space-separated integers: $m_k, Y_{00}, Y_{01}, Y_{11}$.
Here, $m_k$ is a positive integer representing the number of components of the $k$-th type (where $k$ is the type ID). The sum of the numbers of all components will not exceed 10. $Y_{ij}$ represents the output when the two inputs are $i$ and $j$ respectively; $Y_{00}, Y_{01}, Y_{11}$ are three numbers that are either 0 or 1, representing the output of the component when the two inputs are both 0, one is 0 and the other is 1, and both are 1, respectively.
The $(n+2)$-th to $(n+17)$-th lines of the input file represent the function table of the integrated circuit to be constructed. Each line contains 8 numbers, which are either 0 or 1. The first four numbers correspond to the signals of the four inputs (numbered 1–4), and no two lines have the same first four numbers. The last four numbers correspond to the signals that the four outputs should produce when the inputs are the first four numbers.
Output
The output file is digilog.out.
The first line of the file is a word, "Yes" or "No"—if a design scheme meeting the requirements exists, it is "Yes", otherwise it is "No".
If the first line is "No", the file ends. Otherwise:
The second line contains only a non-negative integer $p$, representing the minimum number of gate circuits required. The following $p$ lines each provide a description of the connection of a gate circuit in the circuit. Each line contains four space-separated positive integers: $S, K, A, B$.
Here, $S$ represents the ID of the gate circuit (all used gate circuits are numbered $5 \sim p+4$, with $1 \sim 4$ used to represent the four inputs); $K$ represents the type ID of the component (according to the order in the input file, $1 \sim n$); $A$ and $B$ represent the IDs of the gate circuits or decoding circuit inputs connected to the two inputs of this component (where $A < S, B < S$).
The last line contains four positive integers, representing the IDs of the components (between $1 \sim p$) to which the four outputs of the constructed decoding circuit are connected.
Examples
Input 1
1 5 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1
Output 1
Yes 3 5 1 2 1 6 1 3 2 7 1 4 3 5 6 7 4
Note
The circuit connection for the example output is shown below:
