题目描述

一个异或门有两组输入并产生一组输出：

如果一个有 $n$ 个输入 $1$ 个输出的由异或门构成的系统满足下列条件，那么称它为异或网络：

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

一个网络的输入端从 $1$ 到 $n$ 编号。每个引脚的高低电位由一个长度为 $n$ 的 01 字符串给定。我们假设第 $i$ 个字符代表着第 $i$ 个输入引脚的电位。对于每一组输入电位，网络产生一个输出电位，用 01 表示。注意到每组输入的字符串都是一个代表自然数的二进制串，所以我们可以把输入的字符串按照它们代表的自然数的大小排序。我们会发送固定范围内的自然数到输入端，然后记下有多少次返回了 $1$。

你的任务：

写一个程序：

• 读入关于异或网络的描述：输入引脚数量 $n$，异或门数量 $m$，连接到网络的输出引脚的异或门编号，以及异或门的连接方式；
• 读入两个长度为 $n$ 的二进制串，代表上下区间；
• 计算区间内有多少组输入会使网络返回 $1$；
• 输出答案。

输入格式

第一行，$3$ 个整数：输入引脚数量 $n$ ，异或门数量 $m$，连接到网络的输出引脚的异或门编号。

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

输出格式

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

5 6 5
-1 -2
1 3
1 -2
2 -3
4 6
-4 -5
00111
01110

5

数据规模与约定

对于 $100\%$ 的数据，$3\le n\le 100$，$3\le m\le 3\times 10^3$，输入门从 $1$ 到 $m$ 任意编号。