Simulating SHOI Neural Tissue

This problem involves simulating a new type of neural tissue called SHOI. A SHOI tissue is composed of several SHOI cells forming a tight tree structure. Each cell has exactly one output branch, called an axon, and exactly three input branches, called dendrites. For non‐root cells, the axon is connected to the dendrite of its parent cell. Any dendrite that is not connected to a child cell receives an external input provided as part of the input data.

Each SHOI cell receives exactly three signals (each signal is either \(0\) or \(1\)) and outputs the value which appears most frequently among these three. In other words, if we denote the three inputs as \(a, b, c\), the output is \(1\) if \(a+b+c \ge 2\) and \(0\) otherwise.

The root cell’s output is considered to be the output of the whole tissue.

inputFormat

The input begins with an integer \(n\) representing the number of SHOI cells. The following \(n\) lines describe each SHOI cell in order from cell \(1\) to cell \(n\). Each line starts with an integer \(m\) (\(0 \le m \le 3\)), which is the number of children of that cell, followed by \(m\) space-separated integers representing the indices of its children.

After these \(n\) lines, there is one additional line containing a series of external input values (each either 0 or 1). For each cell \(i\), the number of external inputs provided equals \(3 - m_i\) (where \(m_i\) is the number of children of cell \(i\)), and the external inputs are given in the order of cell indices from \(1\) to \(n\).

outputFormat

Output a single integer (either 0 or 1), which is the output of the root SHOI cell and, hence, the output of the entire tissue.

sample

3
2 2 3
0
0
1 0 1 1 0 0 1

1