C. Functions (1000 points)

Besides roaming the country with his motorcycle gang, Bertie has a daytime job as a QA engineer at a market lead semiconductor company. In this task you are asked to help him by optimizing integrated circuit testing procedures.

Manufacturing large quantities of complicated integrated circuits is a challenging task. A large production run of ICs may only have a few faulty pieces (due to unexpected errors in materials or processes).

   measurement tools
The cost of such failures is higher if the problem is recognized later, when the chips are already embedded in consumer products. Thus, in some situations, it is cheaper to test all chips right after manufacturing, and remove faulty ones before they're shipped. The test process must be as fast as possible, to keep costs down.

Your task is to design minimal test scripts for stateless digital circuits.

You're given descriptions of 10 different IC models to test. Each is given as a netlist, and a list of potential bugs and their frequency in percent - i.e. how likely a malfunctioning or short circuit occurs on a component.

For each product, your submission should be a list of test cases: digital inputs that are delivered to the circuit, and the expected outputs that it should generate.

We run the submitted test case list on a huge amount of circuits (of which we know whether they're faulty or not). For each model, we have a fixed set of reference circuits manufactured for the test run.

For each circuit, the digital inputs in the list are sent to the circuit, and the measured digital outputs are compared to the references specified in the submission. If every digital input specified in the test yields the digital output that matches the reference output submitted, the test considers the circuit faultless; if there is at least one digital output that's different, the test considers the circuit faulty.

If the test answers properly whether the circuits are faulty or not for at least 99.9% of all circuits, the submission passes; otherwise it's a failure.

Product files (problem input)

Header of the product file is
N C I O
i1 i2 ... in
o1 o2 ... on
D1 D2 D3
First line contains the number of networks (N), total number of components (C), number of input components (I) and number of output components (O). The next two lines are listing the input and the output component IDs.

The fourth line lists statistical probability of presence of different defects given in percents: 0.1 means 0.1%, that is every 1000th gate manufactured will have that specific problem. Note: since a single circuit consits of multiple gates, it means a given instance of the circuit may have multiple defect gates. Possible gate-defects are, in the same order as listed in the defect-line:

  1. inverted output (D1)
  2. output is always zero (D2)
  3. output is always one (D3)

The rest of the file describes each network (network is a wire connected to multiple components) in a separate line.

n c1 c2 ... cn
First integer is the number of components connected to that network, the remaining of the line is a list of component IDs. The first component is always the electrical source for that network (a component's output), the rest of the components are all sinks (inputs).

The circuit is composed of three different component types:

Sources are always strong enough to drive all connected sinks, carrying out changes so fast that the logic value of the network is always 0 or 1 and never floating.

Submission format

Teams submit plain text test patterns. Each line of the output contains I + O numbers describing the bits of the tested input-output pair. Bits are listed as 0 or 1 and are separated by a space and are listed in the same order as input and output components appear on the input and output lists on the netlist.

Example input

Product file (problem input):
6 7 2 1
5 6
4
0.1 0.1 0.1
3 1 0 0
2 2 1
2 3 1
2 0 4
3 5 2 2
3 6 3 3

Example output

A valid solution:
0 0 1
1 0 0
0 1 0