Guidance Gates

The heat shield held. The plasma faded to a dull glow, then nothing, and the observation cameras showed blue sky for the first time in months. It was the morning of Eid el-Fitr, and through the viewport the coastline of Algeria was rising to meet them, sunlit and impossibly green after all that time in the dark.

But the landing guidance system went dark three minutes into the descent. The circuit board that fed star-tracking data to the navigation computer had taken damage from the same cosmic radiation that nearly overwhelmed the heat shield. The board was a dense network of logic gates, AND, OR, XOR, and their negated counterparts, wired in sequence to process binary signals from the star tracker and produce the heading corrections the autopilot needed. Every output was wrong. Without accurate readings, the autopilot would miss the landing zone entirely.

There was no time to rewire anything and no spare boards on the ship. The only option was to swap gate types, change an AND to an OR, a NAND to a NOR, whatever it took. Adel needed to simulate the damaged circuit to see what it was actually producing, then find the smallest number of gate swaps that would make the output match what the guidance system expected. Below them, the city where their families were waiting for Eid grew larger by the second.

Input Format

• Line 1: I G where I is the number of input wires and G is the number of gates.
• Line 2: B1 B2 ... BI, the input wire values (each 0 or 1), space-separated.
• Lines 3 to G+2: Each gate: GATE_TYPE IN1 IN2 OUT where GATE_TYPE is one of AND, OR, XOR, NAND, NOR, or XNOR.
• Line G+3: T1 T2 ... TK, the target output values for Part 2 (each 0 or 1).

Wire IDs 0 to I-1 are inputs. Gates produce wires I and above, listed in topological order. The last K wires (highest IDs) are the circuit's outputs.

I <= 100, G <= 10,000. The circuit is a DAG (no feedback loops).

Gate Truth Tables

The gate types follow standard Boolean logic:

Simulate the circuit: propagate input values through all gates in order, computing each output from its inputs using the gate behavior rules described above.

After simulation, collect the output wire values (the last K wires). Encode them as a binary number:

Result = O_1 * 2^(K-1) + O_2 * 2^(K-2) + ... + O_K * 2^0

where O_1 is the first output (lowest output wire ID) and O_K is the last output (highest output wire ID).

Output: The result as a single integer.

Example Input

3 5
1 0 1
AND 0 1 3
OR 1 2 4
XOR 3 4 5
NOR 3 4 6
OR 5 2 7
0 1

Example Walkthrough

Inputs: wire 0 = 1, wire 1 = 0, wire 2 = 1.

Outputs: wire 6 = 0, wire 7 = 1. Binary 01 = 1.

What is the binary-encoded output of the circuit?