P4332 [SHOI2014] 三叉神经树

计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做 SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。 SHOI 组织由若干个 SHOI 细胞构成，SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 $0$和 $1$ 两种。每个 SHOI 细胞根据三个输入端中 $0$和 $1$ 信号的多寡输出较多的那一种。 现在给出了一段 SHOI 组织的信息，以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。

无

无

- 对于 $10 \%$ 的数据，满足 $1\le n \leq 10^3$，$ 1\le q \leq 10^3$。 - 对于 $30 \%$ 的数据，满足 $1\le n \leq 10^5$，$ 1\le q \leq 10^5$。 - 对于 $100 \%$ 的数据，满足 $1\le n \leq 5\times 10^5$，$ 1\le q \leq 5\times 10^5$。