2913 - [Poi1997]XOR Gates

一个异或门有两组输入并产生一组输出： input 1 input 2 output 0 0 0 0 1 1 1 0 1 1 1 0 如果一个有n个输入1个输出的 由异或门构成的系统 满足下列条件，那么称它为异或网络：

1. 网络的每个输入端和至少一个异或门的输入端相连接
2. 每个异或门的输入端和网络的输入端或者某个异或门的输出端相连
3. 只有一个异或门的输出端和网络的输出端相连
4. 每个异或门的输出端要么和至少一个异或门的输入端相连，要么和网络的输出端相连
5. 存在一个对异或门的编号方式，使得对每个异或门的每个输入端都连接到网络的输入端 或者 一个编号更小的异或门的输出端 例如：

第一行，3个整数：输入引脚数量n，异或门数量m，连接到网络的输出引脚的异或门编号 接下来m行代表异或门的连接方式，在这里的第i行代表第i个异或门的两个输入端，输入在[-n, m]的两个数：如果是-k那么连接到第k个异或门的输入脚，否则连接到输出脚。 最后有两行n位的字符串，代表着上下区间。假设给定的字符串长度不超过 100000

一个数：对于给定区间内的输入，有多少个会得到1